in reply to Re: Challenge: Detecting sequences.
in thread Challenge: Detecting sequences.

Is the given period a Mersenne prime

Yes (and thank you for your response). But ...

The value appears to be derived from the fact that the MT retains (and twists) 19937 bits of state: 624 x 32-bit words; of which 31-bits (which move with each iteration) are ignored.

I've read and re-read the descriptions of the MT (and its "proven" capabilities) many times over the years; but the process by which a periodicity of ~4e6001 can be proven escapes me. The various descriptions of the underlying basis of the proof -- a mechanism termed: inversive decimation -- go way over my head.

I was hoping, that the first part of my challenge would elicit a layman's description of it, but it seems that large numbers of the (self-proclaimed) mathematicians around here are only such in the same sense as my 9 y/o niece is a violin virtuoso. She can read the notion and play all (within the limitations of her small hands) the notes in time with the metronome, but she is neither Stephane Grappelli nor Yehudi Menuhin.

The second part of my challenge was actually of most interest to me. I suspect that the use of a Rabin–Karp style rolling checksum might be a practical approach for sequences up to say 1 or 2 billion in length; but I can't see an algorithmic approach that will get much beyond that in a realistic amount of time.

Hence the first part of my question. I was hoping that if I understood inversive decimation, it might be applicable to the non-deterministic generator I am playing with; but it seems (from the further reading I've done thanks to the links posted in this thread) that ID is only possible due to the special nature of the Mersenne prime bits of state.


With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.