Hi!
It is a general observation, that while some values for k give a good
harvest of new primes, others give very little.
This is obvious if you look at the tables of primes of the form k*2^n-1
in Riesel�s book on primes.
I have run thru a number of runs, and I have got from 0 to 8 primes.
Torbj�rn Alm
[EMAIL PROTECTED]
----- Original Message -----
From: "Andy Hedges" <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Tuesday, June 26, 2001 10:47 AM
Subject: RE: Mersenne: Proth observations
> Anyone have any idea why for k = 659 there are very little primes? In fact
> for k up to 200000 there are none (I haven't found any in this range
yet!).
>
> Andy
>
> -----Original Message-----
> From: [EMAIL PROTECTED]
> [mailto:[EMAIL PROTECTED]]
> Sent: 23 June 2001 02:17
> To: Gordon Bower; [EMAIL PROTECTED]
> Subject: Re: Mersenne: Proth observations
>
>
>
>
> 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
> _________________________________________________________________________
> Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
> Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
>
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
