> >I think we should check the math first. I have a sneaky suspicion that
looping
> >won't occur in the relevant region (the first 2^n-3 iterations) unless n
is
> >composite - which may be interesting, but doesn't help us eliminate
Mersenne
> >numbers as candidate primes. But my math is inadequate to prove this 8-(
> I think that you mean n-2 iterations, but you may be right. It's hard to
> say, without any evidence, or solid math.
Think of it like this.
Define L(n)=(2+sqrt(3))^n+(2-sqrt(3))^n. It turns out that what we usually
call *the* Lucas sequence is just
S(n)=L(2^n).
The whole point of the proof is to show that the set of elements a+b.sqrt(3)
(a, b mod N) that form a closed group under multiplication has the maximal
order, N^2-1, and thus N is prime. The Lucas sequence does this with a
little jiggery-pokery, because it is sufficient to show that L(N+1) is zero,
while L((N+1)/q) isn't for any prime factor q of N+1. For Mersenne numbers
the only factor to worry about is 2, so the test collapses into its briefer
form.
So the question becomes one of solving (2+sqrt(3))^n has zero surd part, and
in fact prove that the group does not have order N^2-1. The sequence L(n)
"will" recur in that case. However, it is not difficult to prove that the
"first" recurrence, ie the point where L(x)=L(1), will generally occur quite
late in the sequence unless N has all small factors - in which case, we
would have eliminated this N by trial factoring.
Remember too, this is late in the "L" sequence, not in the S sequence!
Suppose for instance it occurred between L(2^(n-3)) and L(2^(n-2)) - which,
even assuming the "first" recurrence is equally likely anywhere, would occur
with probability 50%. The S-sequence would not even see it.
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!
Chris Nash
Lexington KY
UNITED STATES
=======================================================
Co-discoverer of the 7th and 10th largest known primes.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
