Looping Random Number Generator

Question

I'm not even sure if this is even possible, but I think it's worth a shot.

The Challenge

Code/conceptualize a pseudo-random number generator that has the potential to produce results evenly spaced out with similar frequencies... with a twist. The random number generator has to 'loop' back after Foo iterations to its beginning state then produce the exact same results. Foo is a variable of all positive integers.

For example, if the iterations amount is 4 and the random numbers generated after 4 iterations are {93,5,80,13}, then the next 4 iterations will produce {93,5,80,13}, as will the next 4 after that and so on.

Limitations

1. Random numbers can't be pre-defined. For example, the algorithm can't simply iterate over {1,2,3,4,...int.MaxValue}, up to the iteration amount then go back to the first value.
2. Similar to Limitation 1, random numbers can't be cached so a set of numbers can't be generated, saved, then repeatedly returned.
3. Similar to Limitation 2, the random number generator can't be 'forced' back to a certain state. Beginning seed numbers and whatnot cannot be saved.
4. The RNG can't use the number of iterations its run.

In other words, the Generator has to arrive back at its beginning state solely through consecutive calculations.

Objective

Shortest code wins!

Answer 1

J

I think the simplest solution to this would be the slightly bendy

   p =: 0
   random =: 3 : '(p =: y | >: p) } ?. y # 0'

That is used like this:

   random 5
0.329284
   random 5
0.335644
   random 5
0.985972
   random 5
0.0583756
   random 5
0.038363
   random 5
0.329284

This can be easily modified to provide integers, just change the 0 to whatever value you want as a maximum. Alternatively, one might write the following code:

   p =: 0
   random =: 4 : '(p =: y | >: p) } ?. y # x'

Used like this:

   10 random 5
8
   10 random 5
6
   10 random 5
5
   10 random 5
4
   10 random 5
6
   10 random 5
8

How this works

This uses the J primitive ?.: the statically seeded random number generator; as opposed to ?: the dynamically seeded random number generator. This makes sure the outcome is always the same when run with the same arguments. p is just a simple array pointer here, that gets incremented with every run of the function, up to a maximum of y: the left argument. Every time this code is executed, a list of y random numbers is generated (to comply with the rules). Yes, I do realize this is very much on the edge of the phrasing of the question and that it is most likely against the spirit of the question.

Answer 2

Python

Edit

Since the approach below does not satisfy the criterion, I give an even simpler method Full Cycle, which always produces a full cycle:

def generatePeriodic(seed, period):
    x = seed
    increment = findSmallestCoPrime(period)
    while True:
        x = (x + increment) % period
        yield x

This method always yields all values from [0, period - 1] and then repeats itself. Here findSmallestCoPrime is a function that returns the smallest prime p for which gcd(p, period) = 1 holds.

Previous approach

def generate(seed):
    a = 2 * 5 * 7 + 1
    c = 1
    m = 2 * 5 * 7 * 7
    x = seed % m
    while True:
        yield x
        x = (a * x + c) % m

This is a basic Linear congruential generator, with a period m. m is in this case 490.

The restrictions are:

1. 0 < m
2. 0 < a < m
3. 0 <= c < m
4. 0 <= seed < m

Linear congruential generator has full period for all seed values if and only if:

1. c and m are coprime,
2. a - 1 is divisible by all prime factors of m, and
3. a - 1 is a multiple of 4 if m is a multiple of 4.

With the following, we can choose (almost) any period m, and modify the code accordingly. We always choose c = 1, to satisfy the first point. Then we factorize m = p_1 ^ k_1 * p_2 ^ k_2 * ... * p_n ^ k_n, and we set a = p_1 * p_2 * ... * p_n + 1. So we satisfy the second point. Finally, if m % 4 == 0 we set a new value to a = 2 * (p_1 * p_2 * ... * p_k) + 1 (here note, that (p_1 * p_2 * ... * p_n) % 2 == 0). With this, we satisfy the third point (and the second point is still satisfied).

The only values of m that can not generate a Linear congruential generator are of type: m = 4 * p_1 * p_2 * ... p_n, where p_i != 2. This is because in such cases we get a = m + 1, which violates the second point of restrictions.