Returning random integer from interval based on last result and a seed

Suppose we have an interval of integers [a, b]. I would like to have a function that returns random members from within the interval, without repetitions. Once that all members within the interval are explored, the function would start to return the same first random sequence again, in the same order.

Example: a=1, b=5

3, 1, 4, 5, 2, 3, 1, 4, 5, 2, 3, 1, 4, 5, 2, ... 

This would be easy to achieve by shuffling an array of all elements between a and b, and repeating it once the array is finished. However, this would take too much memory space, and this is not suitable for my case (I might have millions of elements).

Instead, the function I’d like to have would be more or less like this:

f(a, b, n, seed) -> n+1 


a - start of interval b - end of interval n - last element returned from list seed - self-explanatory n+1 - next random element from list, calculated by using the seed and the last element returned (n) 

The trick is knowing some way to get a non-repeated number from the interval based only on the element returned before and the seed. In the end, it would behave like a circular list randomized at its initialization, but without using memory space.

Complexity of Integer Factorization

In Quantum Information and Quantum Computation by Nielsen and Chuang, they define the complexity class NP as follows (page 142):

A language $ L$ is in NP if there is a turing machine $ M$ with the following properties.

  1. If $ x\in L$ then there exists a witness string $ w$ such that $ M$ halts in the state $ q_Y$ ("yes state") after a time polynomial in $ |x|$ when the machine is started in the state $ x$ -blank-$ w$ .
  2. If $ x \not \in L$ then for all strings $ w$ which attempt to play the role of a witness, the machine halts in state $ q_N$ ("no state") after a time polynomial in $ |x|$ when $ M$ is started in the state $ x$ -blank-$ w$ .

This definition is motivated by the factoring decision problem, where they identify "witness strings" $ w$ with possible factors of $ x$ .

My confusion is, based on how NP is defined, it seems like we are able to construct a polynomial time algorithm for solving the factoring decision problem. For a given string $ x$ , start the factoring turing machine $ M$ in the state $ x$ -blank-$ w$ for all $ w < x$ , and check whether the machine ever halts in $ q_Y$ . Since there are $ O(|x|)$ witnesses to check, and for each witness, the machine will halt in polynomial time, it follows that this algorithm will determine whether $ x$ has factors in polynomial time.

Clearly this shouldn’t work, but I am unsure where the flaw in my logic is.

Is deciding solvability of systems of quadratic equations with integer coefficients over the reals in NP?

In the book ‘Computational Complexity’ by Arora and Barak the following question is posed (exercise 2.20.):

Let REALQUADEQ be the language of all satisfiable sets of quadratic equations over real variables. Show that REALQUADEQ is NP-complete.

I know how to show NP-hardness, but I’m stuck when it comes to proving that this problem is in NP, in particular how to show that we can describe a solution using a polynomial number of bits.

I did some research and found out that over the complex numbers, it remains an open question if the problem is in NP [1]. It also seems closely related to the existential theory of the reals, which again is not known to be in NP.

Thus my question: Is this problem known to be in NP? And if so, could somebody point me in the right direction regarding the proof.

[1] Pascal Koiran, Hilbert’s Nullstellensatz is in the Polynomial Hierarchy, Journal of Complexity 12 (1996), no. 4, pp. 273–286.

Java LERP but with integer values

I have a formula which returns a Lerp Vector3 value in integers but the problem is it never reaches the desired target value. It’s converting to pixel values first by multiplying by PPM which is 32.

private Vector3 lerp(final Vector3 source, final Vector3 target, float alpha) {     Vector3 sourcePPM = new Vector3(source.x * PPM, source.y * PPM, 0);     Vector3 targetPPM = new Vector3(target.x * PPM, target.y * PPM, 0);     sourcePPM.x += Math.round(alpha * (targetPPM.x - sourcePPM.x));     sourcePPM.y += Math.round(alpha * (targetPPM.y - sourcePPM.y));     source.x = sourcePPM.x / PPM;     source.y = sourcePPM.y / PPM;     source.z = 0;     return source; } 

So for example with lerp(new Vector3(0.0, 0.0, 0.0), new Vector3(26.0, 29.0, 0.0), 0.06f), the final result is:

Target destination: (26.0,29.0,0.0) Actual final destination: (25.75,28.75,0.0) 

Falling short of the target destination. If I don’t round the values then it gets there fine but I need it to be in whole pixels.

Theoretical lower bound of finding number of occurrences of a target integer in a sorted array

Given a sorted array of integers and a target integer, let’s say we want to find the number of occurrences of the target integer.

It is well-known that a binary search can give time complexity $ O(\lg n) $ where $ n$ is the size of the array. For example, given an array $ [1,2,3,3,4,5]$ and a target $ 3,$ the algorithm should return $ 2$ since there are two copies of $ 3$ in the array.

Question: Is there a faster algorithms which give time complexity less than $ P(\lg n)?$ Otherwise, is there a proof to prove that $ O(\lg n)$ is the theoretical lower bound?

Integer Linear Program as a feasability test

I am a beginner in Integer Linear Programs and I have a question about a problem that I am dealing. This problem tracks a configuration of a graph by unitary transformations on the graph and I want to minimize these number of transformations to achieve another configuration. As I only allow exactly one transformation per step, minimizing the number of transformations is the same as minimizing the number of steps.

But, I enter in the following problem: There is no internal property that can be tracked so that I can check if one or other state is closer or farther from the wanted configuration. That means that I can only check if a specific sequence of transformation is correct in a prior-of-execution defined step, for example, $ T$ . Then, what I am thinking in doing is testing a range of values for $ T$ , as there is a polynomial upper-bound for this value, in increasing order. Then, I will recover the answer of the first $ T$ that gives any answer, as I know it will be a optimal answer.

My questions are:

  • This sort of is a feasibility test for a fixed $ T$ , as if the polytope exists, any answer will be a optimal answer, as they all have the same number of steps $ T$ . This approach is possible? In the sense that it can be calculated given a infinite amount of time? Because I am not sure what is the behavior of a IL program when there is no possible answer (ie. no polytope).
  • If yes, there is some existing technique to deal/optimize this type of situations without finding a specific property?

Given a list of integers and a target integer, return the number of triplets whose product is the target integer and two adjacent triplets

Question: Given a list of integers (possibly negative) and a target integer, return the number of triplets whose product is the target integer and two of the triplets must be adjacent.

More precisely, given a triplet $ (i,j,k)$ with $ i<j<k,$ it satisfies the question above if $ A[i] \times A[j] \times A[k] = target$ and either ($ j = i+1$ and $ k > j+1$ ) or ($ k = j+1$ and $ i < j -1$ .)

For example, if the list given is $ A = [1,2,2,2,4]$ and target $ = 8,$ then the answer is $ 3$ as $ (0, 1, 4) , (1, 2, 3)$ and $ (0, 3, 4)$ are the only triplets satisfying conditions above if we use $ 0$ -based numbering.

I stucked at this question for 3 hours and not able to solve it.

Any hint is appreciated.