Mersenne Digest Saturday, June 30 2001 Volume 01 : Number 865 ---------------------------------------------------------------------- Date: Tue, 26 Jun 2001 09:47:52 +0100 From: Andy Hedges <[EMAIL PROTECTED]> 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 ------------------------------ Date: Tue, 26 Jun 2001 10:09:23 +0100 From: Andy Hedges <[EMAIL PROTECTED]> Subject: RE: Mersenne: Proth observations Are all primes of this form probable primes of this form? Andy - -----Original Message----- From: Hoogendoorn, Sander [mailto:[EMAIL PROTECTED]] Sent: 23 June 2001 10:02 To: '[EMAIL PROTECTED]' Subject: RE: Mersenne: Proth observations Brian J. Beesley Wrote: > My strategy is: > (1) run Proth at medium priority in factoring only mode to eliminate > candidates with "small" factors; For step 1 i use Newpgen. I think this is better configurable then proth in how far or long you want to factor. Don't know which is the fastest of the two. > (2) on the same system, run PRP at low priority to check the > survivors from stage 1 for probable primes; > (3) on a different system (normally running Prime95), run Proth at > medium priority to verify the probable primes. (If you don't have a > "spare" system it would be best to do this in a seperate directory so > as to save keep changing the Proth setup!) > BTW so far _every_ probable prime I've found using PRP has been > accepted as a genuine prime by Proth, though this is certainly not > guaranteed. Same here > If you break the run down as above you will see that some values of k > yield a much smaller proportion of candidates for psuedo-prime > testing than others. Or, to put it another way, some values of k give > a much higher percentage of k.2^p-1 with "small" factors than others. For some k's you have to test more the twice as many candidates in the same range of n's Sander _________________________________________________________________________ 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 ------------------------------ Date: Tue, 26 Jun 2001 19:14:06 +0200 From: =?iso-8859-1?Q?Torbj=F6rn_Alm?= <[EMAIL PROTECTED]> Subject: Re: Mersenne: Proth observations 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 ------------------------------ Date: Tue, 26 Jun 2001 21:08:21 +0200 (MET DST) From: [EMAIL PROTECTED] Subject: RE: Mersenne: Proth observations Andy Hedges <[EMAIL PROTECTED]> asks: > 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!). Let k = 659. If n == 1 (mod 2) then k*2^n == 1 (mod 3) If n == 2 (mod 4) then k*2^n == 1 (mod 5) If n == 0 (mod 3) then k*2^n == 1 (mod 7) If n == 4 (mod 12) then k*2^n == 1 (mod 13) If n == 8 (mod 9) then k*2^n == 1 (mod 73) Therefore, if k*2^n - 1 is prime, then n == 20 or 32 (mod 36). Other useful congruences include If n == 2 (mod 5) then k*2^n == 1 (mod 31) if n == 0 (mod 23) then k*2^n == 1 (mod 47) This doesm't explain the total lack of primes, but shows that many potential n can be eliminated early. _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 27 Jun 2001 18:27:36 +0200 From: Guillermo Ballester Valor <[EMAIL PROTECTED]> Subject: Mersenne: New Glucas v.2.8a Hi: A new version of Glucas has been released. You can download the new version source at sourceforge http://prdownloads.sourceforge.net/glucas/Glucas-2.8a.tar.gz I will also be uploading precompiled binaries when possible. You can see all the files at https://sourceforge.net/project/showfiles_php?group_id=24518 The new features from v.2b are: -Some improvements in computing the physical address from logical addresses. It speed Glucas up about 3-5%. -The old option Y_MINIMUM to compute only the basic power of twiddle factors has been optimized and it can save some additional 3-5% for some machines. -The code has been prepared to begin the introduction of prefecth hints. At the moment we only can enjoy with pentium3 and Athlon prefetch features. It has improved the performance more than 15%. As example, for Athlons Glucas v2.8a with roundoff check activated is as fast as mprime v.20.6 with roundoff active. (the penalty to use the roundoff in Glucas is only 2-4%). Obviously, last improvements introduced by G. Woltman in his last 21.1 version make mprime faster :). -Selftest now has the roundoff check active during first 50 iterations. The second half of selftest has roundoff check disabled. So we can see the timings with both options. For some additional information you can visit http://glucas.sourceforge.net/ I would like to give public acknowledgments to all people who has help me making this release possible. Special thanks to B.J. Beesley, Tom Cage and Klaus Kastens by their suggestions and QA work. Regards. Guillermo. - -- Guillermo Ballester Valor [EMAIL PROTECTED] Granada (Spain) _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 27 Jun 2001 21:11:12 +0200 From: =?iso-8859-1?Q?Torbj=F6rn_Alm?= <[EMAIL PROTECTED]> Subject: Re: Mersenne: Proth observations This is in line the the existence of Sirpinski numbers (no primes exists) and Riesel numbers for k*2^n+1. They are proved by means of congurences. The following values of k have given an exceptional harvest: 753 (9 primes up to 48000), 755 (8 primes up to 48000), 765 (9 primes up to 48000). Other good k-values are 783, 789, and 885. I guess that a congurence analysis will find much fewer eliminating congurences. Torbjörn Alm - ----- Original Message ----- From: <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Tuesday, June 26, 2001 9:08 PM Subject: RE: Mersenne: Proth observations > > Andy Hedges <[EMAIL PROTECTED]> asks: > > > 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!). > > Let k = 659. > > If n == 1 (mod 2) then k*2^n == 1 (mod 3) > If n == 2 (mod 4) then k*2^n == 1 (mod 5) > If n == 0 (mod 3) then k*2^n == 1 (mod 7) > If n == 4 (mod 12) then k*2^n == 1 (mod 13) > If n == 8 (mod 9) then k*2^n == 1 (mod 73) > > Therefore, if k*2^n - 1 is prime, then n == 20 or 32 (mod 36). > Other useful congruences include > > If n == 2 (mod 5) then k*2^n == 1 (mod 31) > if n == 0 (mod 23) then k*2^n == 1 (mod 47) > > This doesm't explain the total lack of primes, but > shows that many potential n can be eliminated early. > > > _________________________________________________________________________ > 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 ------------------------------ Date: Wed, 27 Jun 2001 22:46:19 +0200 From: "Hoogendoorn, Sander" <[EMAIL PROTECTED]> Subject: RE: Mersenne: Proth observations Andy Hedges wrote: > 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!). This number has bees searched till at least 270000 Take a look at http://www.prothsearch.net/rieselsearch.html _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 27 Jun 2001 23:58:32 +0200 From: =?iso-8859-1?Q?Torbj=F6rn_Alm?= <[EMAIL PROTECTED]> Subject: Re: Mersenne: Proth observations Hi! To do a congurence analysis is fairly simple by means of some math program. For k-values of interest, I generated k*2^n-1 for n=0 to 30. Then I factored the values. In this table, the cyclic behavior becomes very obvious. A number of small factors will occur. The table for 885 was interesting. Out of 30 number, 14 were primes! Torbjörn Alm - ----- Original Message ----- From: "Torbjörn Alm" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Wednesday, June 27, 2001 9:11 PM Subject: Re: Mersenne: Proth observations > This is in line the the existence of Sirpinski numbers > (no primes exists) and Riesel numbers for k*2^n+1. > They are proved by means of congurences. > > The following values of k have given an exceptional harvest: > > 753 (9 primes up to 48000), > 755 (8 primes up to 48000), > 765 (9 primes up to 48000). > > Other good k-values are 783, 789, and 885. > > I guess that a congurence analysis will find much fewer > eliminating congurences. > > Torbjörn Alm > > > ----- Original Message ----- > From: <[EMAIL PROTECTED]> > To: <[EMAIL PROTECTED]> > Sent: Tuesday, June 26, 2001 9:08 PM > Subject: RE: Mersenne: Proth observations > > > > > > Andy Hedges <[EMAIL PROTECTED]> asks: > > > > > 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!). > > > > Let k = 659. > > > > If n == 1 (mod 2) then k*2^n == 1 (mod 3) > > If n == 2 (mod 4) then k*2^n == 1 (mod 5) > > If n == 0 (mod 3) then k*2^n == 1 (mod 7) > > If n == 4 (mod 12) then k*2^n == 1 (mod 13) > > If n == 8 (mod 9) then k*2^n == 1 (mod 73) > > > > Therefore, if k*2^n - 1 is prime, then n == 20 or 32 (mod 36). > > Other useful congruences include > > > > If n == 2 (mod 5) then k*2^n == 1 (mod 31) > > if n == 0 (mod 23) then k*2^n == 1 (mod 47) > > > > This doesm't explain the total lack of primes, but > > shows that many potential n can be eliminated early. > > > > > > _________________________________________________________________________ > > 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 ------------------------------ Date: Wed, 27 Jun 2001 17:41:48 -0500 From: "Tom Cage" <[EMAIL PROTECTED]> Subject: Mersenne: Glucas for the Macintosh Glucas for the Macintosh by Guillermo Ballester Valor http://glucas.sourceforge.net Version 2.8a released on Wednesday, 27 June 2001 Clients for G3 and G4, Mac OS 9.1 along with complete source code and project may be found at http://www.belchfirecomputing.com/GIMPS/GIMPS.html Tom _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 27 Jun 2001 20:10:25 -0500 From: "Tom Cage" <[EMAIL PROTECTED]> Subject: Mersenne: Glucas for Mac UNIX FreeBSD 4.4 Glucas for Mac UNIX FreeBSD 4.4 by Guillermo Ballester Valor http://glucas.sourceforge.net Version 2.8a released on Wednesday, 27 June 2001 The UNIX/gcc version runs up to 16% faster than the Mac OS 9/Codewarrior version. The UNIX version also supports full multitasking, Complete source code may be found at http://www.belchfirecomputing.com/GIMPS/GIMPS.html Binaries on request. Tom _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 30 Jun 2001 20:16:36 +0200 From: "Guido Lorenzini" <[EMAIL PROTECTED]> Subject: Mersenne: 33mio exponents Today, during this wonderful Saturday, I've spent some time looking about the Assigned Exponents Report file, in particular the one fixing the situation at 30 Jun 2001 15:00 (Jun 30 2001 8:00AM Pacific), 6 PM here in Italy. I would like to to make some preliminary remarks, 'cause my english, surely all but not perfect, may easily misinterpreted: I'm writing to this list just for satisfying some curiosities, and without any polemic spirit or willing of crossing the swords with anybody! 1st observation: the "beerman's" computer named SKA4 seems to work simultaneously on 4 33mio exponents, since each exponent is getting iterations: how it come? If any Cpu is best working on just one copy of prime95, even a dual cpu PC should have 2 computer ID...You may see the same situation with DEJEFLATERIC of netconx, but, once again, these are just examples. 2nd: Sometimes it happens that an exp. is assigned to an unspecified computer ID (for example, the account "kpgcfd", has some). Is it possible? 3rd: Net_Force seems to have some wonderful machines, called (properly!)10MIL-X: they are able to test (or factoring) dozen of 33mio exponents in 2 months time or more! Any information about the processor of these machines? Or is it relevant the fact bits? (60 or less for these exponents instead 68 or more as usual) 4th: netconx reserved 2,325 33mio exps on its computer ID DEJECHRISTIA, most of them with 60 fact bits or less. It started getting 'em on June 20th at 4:59 AM, one each two minutes, till June 23th at 12:07 PM. Now it may be too long to explain but this mass of 33mio exps. seems to be bounced like a ball from an account to another (e.g. from kpgcfd, ID mac_233, on May to netconcx by now); then these exponents, assigned in June to netconx to computer ID DEJECHRISTIA, were assigned to the same account netconx, but to a machine called BART, in April 7th. I really do not understand what's going on... Is there anybody who may give me some infos about this? I know I've stolen time enough, so nothing more to say but thank you to anyone who may satisfy my curiosity and happy hunting to everybody. Best regards from Italy! Guido _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ End of Mersenne Digest V1 #865 ******************************