Re: Mersenne: Proth observations
Hi! 659 is the currently lowest k-number, where no prime is known. See: www.prothsearch.net/rieselsearch.html Current search limit there in 27. 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 20 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
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 20 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
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 20 there are none (I haven't found any in this range yet!). This number has bees searched till at least 27 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
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 20 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
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
RE: Mersenne: Proth observations
Anyone have any idea why for k = 659 there are very little primes? In fact for k up to 20 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 650k750, it takes about 5 hours for 16000n32000 and 12 hours for 32000n48000 -- 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
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 20 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 650k750, it takes about 5 hours for 16000n32000 and 12 hours for 32000n48000 -- 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
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 20 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
Re: Mersenne: Proth observations
On 22 Jun 2001, at 13:42, Gordon Bower wrote: 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. :) Yes, it does make a change. Anyway, a few curious observations I made, which surprised me: I have 2 computers, a P2-350 and P3-500. The program executes nearly 2 1/2 times as fast on the latter as on the former with nothing else running. Apparently the Proth code takes advantage of a lot of P3 features? Yes, Proth 6.6 has prefetch code for PIII and Athlon CPUs. With the same version of prime95 and the same version of proth on each computer, if you run them both at the same time, under Win2000 proth gets a higher priority and all the processing power, while under NT4, it's the other way round, and prime95 has to be stopped or have its priority reduced in the ini file to not smother proth. Curious. (Why run them both at once, you ask? If the computer is going to be on all night anyway, it'd be idle when proth finished a range unless prime95 was ready to take over as soon as proth was done.) There is a marked difference in the process timeslot allocation algorithm between NT4 W2K. (IMHO neither is as effective as the equivalent function in linux 2.2, further improved in linux 2.4, but that's a different story!) Also between Win95 and Win98. '95 behaves like NT4, and '98 behaves like W2K. Well, only on uniprocessor systems, since '9x/ME don't support SMP at all, but I think you get the drift? My strategy is: (1) run Proth at medium priority in factoring only mode to eliminate candidates with small factors; (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!) (1) takes a lot less time than (2) so even if (2) stops temporarily that's not a problem. Not much survives (2) so run (3) takes little time, even though it's much slower per candidate than the others! 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. 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 650k750, it takes about 5 hours for 16000n32000 and 12 hours for 32000n48000 -- 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? 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. Conversely the slower values of k tend to yield a lot more primes than the faster ones. In fact, if your trial factoring strategy is reasonable, your average rate of discovery of primes will not depend much on the value of k - though it certainly will depend on the average value of n! k.2^p+1 behaves similarly. In fact there are some values of k for which it is _proved_ (mathematically) that there are _no_ k.2^p+1 primes, even though the lowest value of k for which this is true is still uncertain. (Or at least there was still work in progress last time I checked.) You may care to look up the Sierpinski Problem if you're interested in this. A fun project. Now if Michael would just put a stop to that pesky server error I could submit a half dozen more primes to him... :) Yeah, I finished up my raft of blocks a couple of days ago, can't get any more can't report results. No response to mail messages either. He may have gone on vacation. Regards Brian Beesley _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
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
Re: Mersenne: Proth observations
Hey Gordon, At 01:42 PM 6/22/2001 -0800, Gordon Bower wrote: 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. Anyway, a few curious observations I made, which surprised me: I have 2 computers, a P2-350 and P3-500. The program executes nearly 2 1/2 times as fast on the latter as on the former with nothing else running. Apparently the Proth code takes advantage of a lot of P3 features? You should look into newpgen and prp.exe. These two programs can be used to speed up your search for k*2^n+/-1 primes. With the same version of prime95 and the same version of proth on each computer, if you run them both at the same time, under Win2000 proth gets a higher priority and all the processing power, while under NT4, it's the other way round, and prime95 has to be stopped or have its priority reduced in the ini file to not smother proth. Curious. Windows NT and Win2000 users should consider changing prime95's priority to two. There have been reports that idle priority doesn't work as documented in the Microsoft documentation. Regards, George _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Proth observations
Windows NT and Win2000 users should consider changing prime95's priority to two. There have been reports that idle priority doesn't work as documented in the Microsoft documentation. I'd be curious about that... I haven't heard anything, but then I haven't looked either. :) As I've said before, the only time I've ever seen an actual program run slower when Prime95/NT was running is when I'm running any sort of video capture, such as NetMeeting. NetMeeting vid conferences just run DOG slow when I have my ntprime going, but if I stop the service, then the video picks up greatly. I figured that perhaps the codec just ran at idle priority also (which would make sense to me anyway), so you have two CPU intensive things competing for resources... Aaron _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
