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.

Regards,

John Davies

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.

In reply to Re: Challenge: Detecting sequences. by davies
in thread Challenge: Detecting sequences. by BrowserUk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.