mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2006-03-22, 17:30   #12
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

5·17·19 Posts
Default

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. Gerbicz is offline   Reply With Quote
Old 2006-03-22, 17:42   #13
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

11101010101002 Posts
Default

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

Please say something about HOW you arrived at these numbers.
R.D. Silverman is offline   Reply With Quote
Old 2006-03-22, 18:14   #14
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

5·17·19 Posts
Default

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
R. Gerbicz is offline   Reply With Quote
Old 2006-03-24, 00:30   #15
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

25·5·7 Posts
Default

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
philmoore is offline   Reply With Quote
Old 2006-03-27, 21:59   #16
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

350710 Posts
Default

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.
jasong is offline   Reply With Quote
Old 2006-03-28, 14:54   #17
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

11101010101002 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2006-03-31, 00:32   #18
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

3·7·167 Posts
Default

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.
jasong is offline   Reply With Quote
Old 2006-03-31, 03:14   #19
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

3×7×167 Posts
Default

Btw, the second paragraph is tongue in cheek.
jasong is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sieving and LLR-in in same time pepi37 Software 1 2017-05-15 17:17
Prime Density Correction Terms? wblipp Math 20 2011-09-07 21:45
Thanks PG for Sieving, now time to pick a new n? cipher Twin Prime Search 25 2009-08-09 19:32
Prime k-value density rating and factorizations gd_barnes No Prime Left Behind 25 2009-07-30 12:06
Optimal Sieving Time 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔