mersenneforum.org 2^9092392+40291 is a probable prime!
 Register FAQ Search Today's Posts Mark Forums Read

 2011-02-16, 00:47 #45 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 21418 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 101800. The estimated time to prove this number prime via ECPP: 4 trillion years (4x1012.) The estimated time to prove this number prime via strong prp tests should the Generalized Riemann Hypothesis ever be proven: 300 billion years (3x1011.) 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, 01:09   #46
mdettweiler
A Sunny Moo

Aug 2007
USA

22×112×13 Posts

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

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

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10000101101112 Posts

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.

Last fiddled with by TimSorbet on 2011-02-16 at 02:49

2011-02-16, 04:33   #49
philmoore

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

19·59 Posts

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!

2011-02-16, 06:22   #50
gd_barnes

"Gary"
May 2007
Overland Park, KS

101111100011002 Posts

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.

 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, 15:32   #52
wblipp

"William"
May 2003
Near Grandkid

53·19 Posts

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.

2011-02-16, 16:22   #53
axn

Jun 2003

546010 Posts

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.

2011-02-16, 22:19   #54
philmoore

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

100011000012 Posts

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!

 2011-02-16, 22:27 #55 TimSorbet Account Deleted     "Tim Sorbera" Aug 2006 San Antonio, TX USA 10B716 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 sudaprime Miscellaneous Math 11 2018-02-05 08:10 mohdosa Information & Answers 22 2014-10-10 11:34 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 23:59.

Sat Jun 3 23:59:40 UTC 2023 up 289 days, 21:28, 0 users, load averages: 0.88, 0.85, 0.80