>> B: Cycling before the P-1th iteration is unlikely in its own right.
> I thought we had more or less worked out (not formally proved - but a
> solid argument) that if P is prime, cycling _won't_ occur in the
> first P-2 iterations. Pity, because the existence of a cycle in the
> first P-2 iterations _proves_ 2^P-1 composite without having to run
> all the iterations (if it starts cycling, it _can't_ get to 0 at
> iteration P-2)
At the time, Chris Nash said:
"In short, it doesn't matter how you buffer the S-sequence. Suppose you
recorded every residue, that's n-2 steps. There are only (n-2)^2 possible
differences, while in theory the recurrence length could be any of O(N)
lengths. The odds of success are small, we'll call them practically
non-existent. If we are testing M(10,000,000+), then we could at most get
10^14 differences, while the number is as big as 10^3000000."
"The odds of a recurrence occurring make the odds of finding a prime seem
positively good!"
I can send the entire argument to anyone who asks (I don't think these are
in the archives yet.)
Brian J Beesley said that he had a "sneaky suspicion," that they would
recurr only in composite remainders, but there weren't any arguments to
support this.
I agree that this should be put in the FAQ, so that we don't have to
go through this every 1-2 months...
-Lucas Wiman
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
