prime density vs. sieving vs. prp time

[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

[R.D. Silverman]

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

Please say something about HOW you arrived at these numbers.

[R. Gerbicz]

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.

[philmoore]

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

[jasong]

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.

[R.D. Silverman]

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.

[jasong]

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.

[jasong]

Btw, the second paragraph is tongue in cheek.