mersenneforum.org Fourth probable prime found, one to go!
 Register FAQ Search Today's Posts Mark Forums Read

2009-11-23, 17:30   #1
philmoore

"Phil"
Sep 2002
Tracktown, U.S.A.

3×373 Posts
Fourth probable prime found, one to go!

Engracio sent this in last Tuesday:

Quote:
 [Mon Nov 16 19:52:35 2009] 2^5146295+41693 is a probable prime! Wd1: B19D6BB0,00000000
Now that it has passed a number of strong probable prime tests, we can confirm that Five or Bust has now found its fourth probable prime! I will submit it to the Lifchitz site this morning. At 1,549,190 decimal digits, it will become the new largest known probable prime.

I want to note that this is an incredibly lucky discovery! I estimated about a 6% chance of finding another probable prime between the exponent of the previous one, 4583176 and this one, 5146295. I was so surprised when Engracio reported it, but there it is, we can't argue with success! New work files and a new sieve file have been uploaded, now 40291 is the last odd k value < 78557 for which no prime or probable prime of the form 2n+k is known. We eliminated 50.2% of our prp tests, and we now can expect about 0.19166 probable primes in any interval where our exponents double, for example, in the range from n=5.15M to n=10.30M. So we could solve this problem tomorrow, or it could take us a long time! I haven't computed the probabilities yet, but I am sure they have come down, now that we have only one left to find. But the show ain't over till the fat prime sings!

The probability that a random number of this size would be composite after having passed all of these strong probable prime (Miller-Rabin) tests is < 10-1360. I estimate that it would take around 225 billion years to prove it is prime if we could gear up ECCP on a single process, maybe only 60 billion years or so if the generalized Riemann hypothesis were proven. Hopefully, someone will come up with better primality proving algorithms before then.

Here is a graph comparing the progress between this problem and the Sierpinski problem. Note how much the last point has dropped. Dropping like a stone, hopefully...

Let's go find that last probable prime!

Last fiddled with by philmoore on 2009-11-24 at 04:45 Reason: minor typo

 2009-11-23, 17:48 #2 Mini-Geek Account Deleted     "Tim Sorbera" Aug 2006 San Antonio, TX USA 427010 Posts Someone besides paleseptember found one of 'em, for once! The obligatory: I think we should now expect to have to search to 63.17M (63.17M=5.15M*2^(X/.19166) with X such that e^(-X)=0.5) to get a 50% chance of a prime. How lousy. Hopefully the odds are beaten. On the other hand, there's a decent chance this project could find the first 10M+ digit PRP. We shouldn't expect 1 prime until 191.63M. The odds of at least one by then is only about 63.21%. Last fiddled with by Mini-Geek on 2009-11-23 at 18:06
2009-11-23, 18:41   #3
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

2·2,969 Posts

Quote:
 Originally Posted by Mini-Geek Someone besides paleseptember found one of 'em, for once! The obligatory: I think we should now expect to have to search to 63.17M (63.17M=5.15M*2^(X/.19166) with X such that e^(-X)=0.5) to get a 50% chance of a prime. How lousy. Hopefully the odds are beaten. On the other hand, there's a decent chance this project could find the first 10M+ digit PRP. We shouldn't expect 1 prime until 191.63M. The odds of at least one by then is only about 63.21%.
i am not sure we know enough about prime numbers to work out accurate predictions
on this project the predictions keep on being way too high for instance

 2009-11-23, 19:08 #4 engracio     May 2007 112 Posts version 4.0.1 What no ??? Come on guys let's Wohoooooo
 2009-11-23, 19:13 #5 Cybertronic     Jan 2007 Germany 421 Posts Congratulation to your FoB team !!! Norman
 2009-11-23, 22:45 #6 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100101100100102 Posts Wow!
 2009-11-23, 22:58 #7 paleseptember     Jun 2008 Wollongong, .au 3×61 Posts I believe these are in order? Excellent news, fantastic effort for all involved, including the sievers too! They make life so much easier for the PRP-testers. Oh, and I love the new look work-files ;] So much more compact!
 2009-11-23, 23:39 #8 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 100010111112 Posts Thanks to (alphabetically) Ben, Dmitry, Engracio, Geoff, Greg, Hadrian, Jayson, Jeff, Karsten, Kent, Lennart, Max, Phil, Serge, Tim, Winnie, and Yves, all of whom have contributed time either prp testing, sieving, or both. Thanks also to George Woltman for the prp testing software, to Geoff Reynolds for the sieving software, and to Mike Vang (xyzzy) for hosting a home for us. And now, the odds: 10% chance of finishing by 7.5x106 50% chance of finishing by 6.3x107 90% chance of finishing by 2.1x1010 Compare this to http://www.mersenneforum.org/showthread.php?t=12376 to see that our odds have dramatically improved. I don't see any reason that the odds can't improve even more!
 2009-11-24, 00:14 #9 engracio     May 2007 112 Posts Phil, I'd like to know how you feel about his one question. Since we are on the last sequence, how do feel about immediately posting a possible prime candidate for the last sequence so that we/others can immediately start other dc project while awaiting confirmation? In the unlikely event that it is a false positive, the temp stoppage would be a day or so at most.
2009-11-24, 00:43   #10
philmoore

"Phil"
Sep 2002
Tracktown, U.S.A.

21378 Posts

Quote:
 Originally Posted by engracio Phil, I'd like to know how you feel about his one question. Since we are on the last sequence, how do feel about immediately posting a possible prime candidate for the last sequence so that we/others can immediately start other dc project while awaiting confirmation? In the unlikely event that it is a false positive, the temp stoppage would be a day or so at most.
I don't have any problem notifying everyone right away, but I would probably prefer to do it via email or PM than post it on the Forum. I wrote Jeff just a couple of hours after I received your email, telling him to pull all the 41693 numbers from his 5.15-5.16M reservation until we knew for sure, but I also asked him if he would be willing to finish the 5.09-5.10M reservation so that we knew whether your prp was truly the smallest. But if he hadn't wanted to do that, I was willing to finish that set myself. I wrote Ben the day afterwards, telling him the situation and asking if he was willing to finish the 41693 numbers in his 4.97-5.00M reservation, and I also let Kent, who was sieving, know fairly early on. The reason I wanted to finish the smaller numbers is to complete the Sloane sequence A067760 up to (78557-1)/2:
http://www.research.att.com/~njas/se...nguage=english
But if anyone wants to jettison the rest of their tests next time, no problem, I am willing to finish them. The work stoppage may be more than a day or two if the next prp is quite a bit larger, but the prospect of a false pseudo-prime is pretty remote.

Of course, this assumes that the project stays small. If it grows a great deal, it would probably make more sense to do as you suggest.

 2009-11-24, 01:14 #11 Jeff Gilchrist     Jun 2003 Ottawa, Canada 3·17·23 Posts Congrats everyone, great work! Now I'm starting to wonder if paleseptember = engracio as a second account because how is it possible for anyone besides him to find a PRP in this project?!?!?! Just kidding of course, looks like I just missed that reservation. Maybe next time.

 Similar Threads Thread Thread Starter Forum Replies Last Post sudaprime Miscellaneous Math 11 2018-02-05 08:10 Cybertronic Twin Prime Search 18 2011-08-20 13:36 philmoore Five or Bust - The Dual Sierpinski Problem 25 2009-09-09 06:48 philmoore Five or Bust - The Dual Sierpinski Problem 15 2009-02-08 19:43 philmoore Five or Bust - The Dual Sierpinski Problem 18 2009-01-28 19:47

All times are UTC. The time now is 21:23.

Sun Dec 5 21:23:41 UTC 2021 up 135 days, 15:52, 0 users, load averages: 1.45, 1.60, 1.49