all,
>Assuming the LL residues are pseudorandom,
Big assumption, here are the first 10 remainders for n=101 (in binary, of course):
1110
11000010
1001001100000010
1010100011010110100110000000010
1101111010110100101101101100111110000001111010011000000000010
10010100001011110111010101101011111011000110011001000100001000000011110101010000011001111011110111111
11000010111111001001011110011011111011011100111110011101110110000101101101110111111011011111001001000
11100010011000110101110001010000110011110000100100000010001010010010101101011100010000101110101100001
11011110101011110010101001010100001000100100111110011011100011101100011001111101111011110010110111011
They hardly look random, but this is hardly conclusive
>then the repetition length should
>be on the order of sqrt(2^n - 1) =~ 2^(n/2) which is veeeeeery big. It
>doesn't seem likely that any repetition will occur, even in testing googols
>of exponents...
Here is an "intuitive" argument:
We start out with a power of 2: 4
we then proceed to square, subract 2
then we take mod to a series of 1's (in binary), lather rinse and repeat.
The actual l_n values would surely not be random, always ending in 10b, and the
strings of zero's in then would just get longer and longer.
Taking mod a number is (basically) subtraction, and subtracting series of 1b's
wouldn't seem to change the "randomness" of the number.
Also, remember our lord and savior (knuth) said (somewhere in Vol. 2 in the section on
random #'s) "random numbers are not produced through the appication of random
proceses." Just because these operations may seem to have only a tenative
relationship to each other, does not mean that they produce random numbers.)
Best I could come up with ;-). I think that the best course of action would be
to try and find numbers where the remainder actually does repeat (should any exist.)
When checking, we should consider exponents were all the remainders can be saved. The
size of saving all the exponent, in bits is ~n*(n-1), so keeping it <10MB, solve the
quadratic eq. n^2-n-10*8*1024*1024=0, so n is ~9159.
Would anyone be willing to write the code to test this? (I would, but my programing
skills are less than enough, I will however loan my CPU cycles)
-Lucas
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
