2^9092392+40291 is a probable prime! - Page 5

philmoore · 2011-02-16, 00:47

Zuzu made some more careful calculations that I have now repeated, so I now estimate that we would have had about a 14.5% chance of finding the last prime in the range 5146295-9092394 instead of the 17% I wrote above. He also wrote on the Seventeen or Bust Forum that when this project started, at n = 1.4 million, we would have predicted a 0.9% chance of finding all the prps by 9092394. I haven't repeated that particular calculation, but it sounds like it is in the right ballpark. We have been incredibly lucky! Hopefully, some of this luck will rub off on Seventeen or Bust now.

A few other interesting tidbits:

The probability that a random number of this size which has passed these strong probable prime tests is actually composite: something like 1 chance in 10¹⁸⁰⁰.

The estimated time to prove this number prime via ECPP: 4 trillion years (4x10¹².)

The estimated time to prove this number prime via strong prp tests should the Generalized Riemann Hypothesis ever be proven: 300 billion years (3x10¹¹.)

Fortunately, with a billion computers, this would only take 300 years, as the tests can be trivially distributed. Maybe we should start another project!

mdettweiler · 2011-02-16, 01:09

Quote:

Originally Posted by philmoore

Fortunately, with a billion computers, this would only take 300 years, as the tests can be trivially distributed. Maybe we should start another project!

I don't suppose an ECPP proof could be distributed easily? (I know it can be distributed amongst multiple cores of the same computer, but is there any reason why they have to be on the same computer?) Because if it could be done, then that might be the next step for this project: working through the unproven PRPs from the bottom up.

(Perhaps, by the time the biggest ones are reached, computers will be sufficiently faster that the proofs will be within reach by ECPP, or by some faster method if it becomes available by then.)

enderak · 2011-02-16, 01:13

What are we waiting for? I am sure when our successors perfect quantum computing they will appreciate the 0.000001% head start. ;)

TimSorbet · 2011-02-16, 02:49

Quote:

Originally Posted by philmoore

He also wrote on the Seventeen or Bust Forum that when this project started, at n = 1.4 million, we would have predicted a 0.9% chance of finding all the prps by 9092394.

IMHO that strongly suggests something more than luck. Has anyone tested ranges to check if 2^n+k produces more primes than expected over any chosen range? It wouldn't be hard to search low n over a broad k range (even if well outside what was needed to prove the conjecture), e.g. such that you can expect 100 or more primes, and compare expected primes to observed to see if the trend holds up.

philmoore · 2011-02-16, 04:33

Quote:

Originally Posted by Mini-Geek

IMHO that strongly suggests something more than luck. Has anyone tested ranges to check if 2^n+k produces more primes than expected over any chosen range? It wouldn't be hard to search low n over a broad k range (even if well outside what was needed to prove the conjecture), e.g. such that you can expect 100 or more primes, and compare expected primes to observed to see if the trend holds up.

Sounds like a worth-while line of investigation. Fix n fairly large so that 2^n >> k, and search a range of odd k. We would expect the density of primes to be roughly 2/(n*ln(2)). Repeat for several values of n. Compare observation with expectation. Were we lucky, or could our luck have been predicted?

By the way, I added a few more names in the "thanks to ..." section of post 38. I can't believe I left out Justin (enderak), as I even mentioned him in the post! Also, Alex, Nathan, and Robert. If anyone else spots any oversights, please let me know!

gd_barnes · 2011-02-16, 06:22

Quote:

Originally Posted by akruppa

Awesome. Congrats to Phil and all contributors.

I'll try to get a few factors out of 2^9092392+40290 so we can make a somewhat stronger PRP test.

Congrats to the Five or Bust project!

What about finding some factors of 2^9092392+40292 ? Would that help with the PRP test for 2^9092392+40291 ? The factor DB has only 2^2*3 for it and I wouldn't know how to begin factoring such a large number.

akruppa · 2011-02-16, 13:49

It would help strengthen a P+1 PRP check. I've done 10 curves at B1=11000 but not found any prime factor >3 yet. I use mprime with

Code:

ECM2=1,2,9092390,10073,11000,0,90,"3"

Did 90 curves at B1=11k, no factor.

wblipp · 2011-02-16, 15:32

Quote:

Originally Posted by philmoore

Sounds like a worth-while line of investigation. Fix n fairly large so that 2^n >> k, and search a range of odd k. We would expect the density of primes to be roughly 2/(n*ln(2)).

Don't you need to account for partial coverings? Some k's are much more likely than others to have primes.

axn · 2011-02-16, 16:22

Quote:

Originally Posted by philmoore

Sounds like a worth-while line of investigation. Fix n fairly large so that 2^n >> k, and search a range of odd k. We would expect the density of primes to be roughly 2/(n*ln(2)). Repeat for several values of n. Compare observation with expectation. Were we lucky, or could our luck have been predicted?

Quote:

Originally Posted by wblipp

Don't you need to account for partial coverings? Some k's are much more likely than others to have primes.

I had done a crude analysis a few years back for SR5 primes (or was it RieselSieve project?) where I calculated the correlation between the weight of a k and index of its first prime. IIRC, the correlation was something like 0.2.

My conclusion was that how many primes a series produces is only weakly predictive of where the first prime would be. So one doesn't necessarily help with the other. Of course, it wouldn't surprise me if the analysis was deeply flawed.

philmoore · 2011-02-16, 22:19

Quote:

Originally Posted by wblipp

Don't you need to account for partial coverings? Some k's are much more likely than others to have primes.

That's why I suggested fixing n and searching a range of k's, with enough k's, we would expect the weights to average out. On the other hand, maybe someone thinks that these particular k's were for some reason, more likely to yield primes at low n. That would be difficult to test, it basically would require extending this project!

TimSorbet · 2011-02-16, 22:27

I am going to search 3<=k<10K (k odd) for 10K<=n<=20K. From doing some calculations on portions of the range sieved to 1M, I expect approximately 10000 primes to be in this range. I'll have a more exact figure when sieving is complete. We'll see how it turns out.

If anyone feels my bounds are a bad representation, they can search elsewhere (and, if they have a good reason why, I might be inclined to stop searching this).

2011-02-16, 00:47	#45
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 1121₁₀ Posts	Zuzu made some more careful calculations that I have now repeated, so I now estimate that we would have had about a 14.5% chance of finding the last prime in the range 5146295-9092394 instead of the 17% I wrote above. He also wrote on the Seventeen or Bust Forum that when this project started, at n = 1.4 million, we would have predicted a 0.9% chance of finding all the prps by 9092394. I haven't repeated that particular calculation, but it sounds like it is in the right ballpark. We have been incredibly lucky! Hopefully, some of this luck will rub off on Seventeen or Bust now. A few other interesting tidbits: The probability that a random number of this size which has passed these strong probable prime tests is actually composite: something like 1 chance in 10¹⁸⁰⁰. The estimated time to prove this number prime via ECPP: 4 trillion years (4x10¹².) The estimated time to prove this number prime via strong prp tests should the Generalized Riemann Hypothesis ever be proven: 300 billion years (3x10¹¹.) Fortunately, with a billion computers, this would only take 300 years, as the tests can be trivially distributed. Maybe we should start another project!

2011-02-16, 13:49	#51
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	It would help strengthen a P+1 PRP check. I've done 10 curves at B1=11000 but not found any prime factor >3 yet. I use mprime with Code: ECM2=1,2,9092390,10073,11000,0,90,"3" Did 90 curves at B1=11k, no factor. Last fiddled with by akruppa on 2011-04-06 at 13:17

2011-02-16, 22:27	#55
TimSorbet Account Deleted "Tim Sorbera" Aug 2006 San Antonio, TX USA 11×389 Posts	I am going to search 3<=k<10K (k odd) for 10K<=n<=20K. From doing some calculations on portions of the range sieved to 1M, I expect approximately 10000 primes to be in this range. I'll have a more exact figure when sieving is complete. We'll see how it turns out. If anyone feels my bounds are a bad representation, they can search elsewhere (and, if they have a good reason why, I might be inclined to stop searching this). Last fiddled with by TimSorbet on 2011-02-16 at 22:30

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
probable largest prime.	sudaprime	Miscellaneous Math	11	2018-02-05 08:10
Hi, how can I test my probable prime number?	mohdosa	Information & Answers	22	2014-10-10 11:34
Megadigit probable prime found, our third!	philmoore	Five or Bust - The Dual Sierpinski Problem	25	2009-09-09 06:48
Another record probable prime found!	philmoore	Five or Bust - The Dual Sierpinski Problem	15	2009-02-08 19:43
Record probable prime found!	philmoore	Five or Bust - The Dual Sierpinski Problem	18	2009-01-28 19:47

2011-02-16, 01:13	#47
enderak Feb 2009 47₈ Posts	What are we waiting for? I am sure when our successors perfect quantum computing they will appreciate the 0.000001% head start. ;)