 mersenneforum.org > Math prime density vs. sieving vs. prp time
 Register FAQ Search Today's Posts Mark Forums Read  2006-03-22, 17:30 #12 R. Gerbicz   "Robert Gerbicz" Oct 2005 Hungary 5·17·19 Posts On Seventeenorbust forum I've made a prediction: I've computed the expected n, when we'll find a prime by 50% probability, if all numbers tested up to exponent=10M then: Remaining=7 will reach at 1.3*10^7 Remaining=6 will reach at 1.8*10^7 Remaining=5 will reach at 2.7*10^7 Remaining=4 will reach at 4.5*10^7 Remaining=3 will reach at 9.5*10^7 Remaining=2 will reach at 3.1*10^8 Remaining=1 will reach at 3.1*10^9 Remaining=0 will reach at 4.5*10^13 This isn't very far from the prediction what Yves Gallot has been done in 2001 ( when there were 17 remaining cases ): there is 50% probability to solve the poblem up to N=2^43 ( it is about 8*10^12 ) For Riesel problem the case is much worse: We have 50% chance of solving Riesel problem at n=2^73. ( Gallot gave the prediction n=2^70 ) I've also calculated that by 5% probability we'll complete the project before n=2^50 and by 5% probability we won't complete before n=2^127. See: http://www.rieselsieve.com/forum/viewtopic.php?t=650   2006-03-22, 17:42   #13
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

11101010101002 Posts Quote:
 Originally Posted by R. Gerbicz On Seventeenorbust forum I've made a prediction: I've computed the expected n, when we'll find a prime by 50% probability, if all numbers tested up to exponent=10M then: Remaining=7 will reach at 1.3*10^7 Remaining=6 will reach at 1.8*10^7 Remaining=5 will reach at 2.7*10^7 Remaining=4 will reach at 4.5*10^7 Remaining=3 will reach at 9.5*10^7 Remaining=2 will reach at 3.1*10^8 Remaining=1 will reach at 3.1*10^9 Remaining=0 will reach at 4.5*10^13 This isn't very far from the prediction what Yves Gallot has been done in 2001 ( when there were 17 remaining cases ): there is 50% probability to solve the poblem up to N=2^43 ( it is about 8*10^12 ) For Riesel problem the case is much worse: We have 50% chance of solving Riesel problem at n=2^73. ( Gallot gave the prediction n=2^70 ) I've also calculated that by 5% probability we'll complete the project before n=2^50 and by 5% probability we won't complete before n=2^127. See: http:/www.rieselsieve.com/forum/viewtopic.php?t=650   2006-03-22, 18:14   #14
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

5·17·19 Posts Quote:
 Originally Posted by R.D. Silverman Please say something about HOW you arrived at these numbers.
OK Here it is the details, it isn't very hard but interesting how we can calculate very fast this for example for Riesel problem:
k*2^n-1 is prime by about w(k)/(n*log(2)) probability, here w(k) is the "weight" of k for Riesel problem and there is a table for this.
So the probability that k*2^s-1 is composite for all A<s<B is about prod(1-w(k)/(n*log(2),n=A,B) but 1-x is very close to exp(-x) for small x values so this product is about c(A,B,k)=prod(exp(-w(k)/(n*log(2)),n=A,B)=exp(-w(k)/log(2)*sum(1/n,n=A,B)) but sum(1/n,n=A,B) is about log(B/A) so c(A,B,k)=(B/A)^(-w(k)/log(2)).
Let f(x,A,B)=prod(c(A,B,k)*x+1-c(A,B,k), for all remaining k values) the degree of the polynom is 73 for Riesel problem ( because there are 73 remaining cases ) and you can see that the coefficient of x^j will give the probability that there will be only j remaining k vaules if we complete the project up to N=B and if we suppose that all exponents tested up to A for all k values. So the probability that there will be at most h remaining cases is the sum of the coefficients of x^j from j=0 to h.

Last fiddled with by R. Gerbicz on 2006-03-22 at 18:17   2006-03-24, 00:30   #15
philmoore

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

25·5·7 Posts Quote:
 Originally Posted by R.D. Silverman The SoB web page shows current test limits of ~13 million. I had either misread or mentally translated that into 1.3 million.
Only a handful of tests have actually been completed around 13.467 million. First time tests currently being handed out are just below 10.5 million. The current test windows are shown at:
http://www.seventeenorbust.com/stats/rangeStatsEx.mhtml   2006-03-27, 21:59 #16 jasong   "Jason Goatcher" Mar 2005 350710 Posts I don't pretend to understand most of the math in this thread, but a while back I came up with what I guess you'd call a hack to attempt to solve the problem. I figured I needed to assign a value to each test. It didn't matter how big or small the value is, they just had to accurately describe the value of a test relative to other tests. I came up with two values to deal with:the time a test takes, which in my instance I used calculations which only had a proportionate relationship to the length of time a test takes. The Sierpenski and Riesel problem have separate ways of attempting to determine primality, so I had to use separate equations for each problem. For the Sierpenski problem, I used the equation 1/((n/ln n)^2). The time a test takes is proportionate to (n/ln n)^2, but given even odds, a shorter test is "worth more." The equation for Riesel problem is 7.5^(ln n/524288)*100,(the value for a test is 1/(7.5^(ln n/524288)*100) but the results for the Sierpenski and Riesel problem are NOT interchangeable. Now for the second value, I used a program called pr_prob, which figured the odds any n will yield prime after a certain amount of sieving. This is also an inverse proportion. I multiplied the numbers together and I got some extremely small values. For the Sierpenski problem, I calculated that unless you could sieve an average of 30 values for every you PRP you should be PRP ing. (My calcuations for the Riesel problem are old, so not dependable) Here's the thread, for those interested, although I made some rather embarrassing false starts.   2006-03-28, 14:54   #17
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

11101010101002 Posts Quote:
 Originally Posted by jasong I don't pretend to understand most of the math in this thread, I came up with two values to deal with:the time a test takes, which in my instance I used calculations which only had a proportionate relationship to the length of time a test takes. The Sierpenski and Riesel problem have separate ways of attempting to determine primality, so I had to use separate equations for each problem. For the Sierpenski problem, I used the equation 1/((n/ln n)^2). The time a test takes is proportionate to (n/ln n)^2, but given even odds, a shorter test is "worth more." The equation for Riesel problem is 7.5^(ln n/524288)*100,(the value for a test is 1/(7.5^(ln n/524288)*100) but the results for the Sierpenski and Riesel problem are NOT interchangeable.
This is mathematical gibberish. And the run-time estimates to test a
single Sierpinski or Riesel Candidate are wrong. I suggest that you
look up the time-complexity function for performing a *single* FFT-based
multiplication, then multiply by the number of multiplications needed
to test a candidate. And what you call "equations" are not equations.   2006-03-31, 00:32   #18
jasong

"Jason Goatcher"
Mar 2005

3·7·167 Posts Quote:
 Originally Posted by R.D. Silverman This is mathematical gibberish. And the run-time estimates to test a single Sierpinski or Riesel Candidate are wrong. I suggest that you look up the time-complexity function for performing a *single* FFT-based multiplication, then multiply by the number of multiplications needed to test a candidate. And what you call "equations" are not equations.
It is most certainly NOT gibberish. I was attempting to come up with a way to calculate the value of a test or group of tests.

Besides, no one else has ever managed to come up with anything to solve this statistical problem, which makes my method best, simply because it's a lone candidate.

You say it's wrong? Tell me why it's wrong. All you've done so far is insult me, which seems par for the course when it comes to R.D. Silverman.   2006-03-31, 03:14 #19 jasong   "Jason Goatcher" Mar 2005 3×7×167 Posts Btw, the second paragraph is tongue in cheek.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post pepi37 Software 1 2017-05-15 17:17 wblipp Math 20 2011-09-07 21:45 cipher Twin Prime Search 25 2009-08-09 19:32 gd_barnes No Prime Left Behind 25 2009-07-30 12:06 jasong Sierpinski/Riesel Base 5 10 2009-01-25 15:56

All times are UTC. The time now is 08:42.

Tue Feb 7 08:42:23 UTC 2023 up 173 days, 6:10, 1 user, load averages: 1.39, 1.29, 1.10