|Just another Perl shrine|
Re: Challenge: Detecting sequences.by davies (Parson)
|on May 10, 2013 at 21:02 UTC||Need Help??|
Is the given period a Mersenne prime (if it's prime, it is a Mersenne prime) or a multiple of several small other primes?
If it is prime and any two numbers in the entire sequence are different, the prime is the period. Take two non-random sets of numbers. The first is 1, 2, 1 and the second 1, 2, 1, 2, 1. Even though these are apparently the same, they will give different sequences. The fifth number from the first set will be 2 and from the second 1. Compare this with non-prime sequences (1, 2 and 1, 2, 1, 2). The period of both of these is 2.
Next, let's imagine that the number generator uses two sets of numbers, drawing one alternately from each set. If the first two sets are used, the period will be 15 because both sets will have to reach the end at the same time before the sequence repeats.
Now, what is interesting is that using the second pair of sets in the way I have described gives a period of 4, not 2. But that isn't guaranteed. So if the period given is simply the lowest common multiple of the periods of the various PRNGs of shorter period, it might be more correct to say that the period is AT LEAST the number given. Alternatively, they might have been able to look at it in the same way as my second two sets of numbers, but if that is the case I'm afraid that the best explanation I can give is "they used maths".
Note that throughout this, I have not been testing for randomness but for period length. If you're testing a single prime sequence of this length for randomness you have to use sampling. But if you're testing a number of smaller sequences, each can be tested in its entirety using things like runs tests and chi squared. Note also that I am not a mathematician, so if anyone wants to tear my argument to pieces, I'd be very interested. I did check this logic with a mathematician once and he said that it was correct (a) if I remember what he said correctly and (b) if I explained it correctly. We'd both had a few beers.
Update: I think the period of my sequence based on the 3 and 5 period sequences is actually 30, not 15. This is because it needs to be multiplied by the number of sequences. But I'll check when I don't need my bed so badly. This might explain why the 2 and 4 number sequences give a combined period of 4.