Fourth probable prime found, one to go!

[philmoore]

Engracio sent this in last Tuesday:

[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 2ⁿ+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!

[TimSorbet]

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%.

[henryzz]

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

[engracio]

version 4.0.1

What no ???

Come on guys let's


Wohoooooo

[Cybertronic]

Congratulation to your FoB team !!!

Norman

[Batalov]

Wow!

[paleseptember]

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!

[philmoore]

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.5x10⁶
50% chance of finishing by 6.3x10⁷
90% chance of finishing by 2.1x10¹⁰

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!

[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.

[philmoore]

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.

[Jeff Gilchrist]

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.