Gordon Bower <[EMAIL PROTECTED]> observes
> After seeing a post on this list a few weeks ago I decided to branch out
> and try a few ranges from Michael Hartley's page looking for k*2^n-1
> primes. I must say there is a bit of a thrill in actually discovering a
> new prime every day I run the program instead of proving two numbers a
> month composite. :)
> I assumed that one value of k was pretty much the same as any other as far
> as execution time and the chance of finding primes. To my surprise this
> turned out not to be so: On the P3-500, for "most" 650<k<750, it takes
> about 5 hours for 16000<n<32000 and 12 hours for 32000<n<48000 -- but for
> k=701 it took less than 2 and just over 6 hours, respectively. The
> phenomenon is reproducible, doesn't seem to be an artifact of other
> programs or reboots or suchlike. Any number theorists care to explain what
> is special about k=701 that makes it easy to check for primality?
>
Fix k = 701. We check that
If n == 1 (mod 2) then k*2^n == 1 (mod 3)
If n == 0 (mod 4) then k*2^n == 1 (mod 5)
If n == 6 (mod 8) then k*2^n == 1 (mod 17)
If n == 0 (mod 3) then k*2^n == 1 (mod 7)
Therefore k*2^n - 1 can be prime only if n == 2 or 10 (mod 24).
We can eliminate more potential values of n using
If n == 8 (mod 18) then k*2^n == 1 (mod 19)
If n == 18 (mod 20) then k*2^n == 1 (mod 41)
If n == 6 (mod 28) then k*2^n == 1 (mod 29)
Some congruences are redundant; for example
If n == 6 (mod 12) then k*2^n == 1 (mod 13)
eliminates nothing new. k = 701 has less such redundancy than
the typical k.
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
