The real linear congruential number generators are more complicated but it is possible to generate a sequence that hits every number in 32 bits using only:
seed = seed * m + a
Obviously if m = 0 and a = 0, the sequence has length 1 if m = 1 and a = 1, the sequence counts through the entire range.
I experimentally determined that there are many numbers m and a around 32k, which must be odd, that have this property. For example (from memory, hopefully I am right)
m = 32097, a = 31079
I wrote a small program and discovered that if m has this property, then there are many primes a that will work.
I do not yet know if for a working m, all prime numbers (except 2) will work. I will test that empirically, but wondered whether there is some theory that would prove the results.
On the computer, I test that the sequence hits every number by the following simple test:
1. start with seed = 0
2. count 2^32 times. For each time, calculate step 3
3. seed = seed * m + a
4. if seed == 0, break out, the sequence ends early
5. if after 2^32 iterations the sequence ends in 0, then every number must have been reached.
This mechanical proof won't work well for 64 bit numbers, so if anyone can prove that this is true, is there a way to determine the numbers m and a for which this will work without trying all 2^64 values?