prime density vs. sieving vs. prp time
 

I'm not totally sure what information is required to figure this out, but here's the problem:

In the Sierpenski problem and the Riesel problem we are basically trying to combine the k with an n that makes it prime. I'm hoping you can help me come up with a formula that incorporates the sieving efficiency, the odds of finding a prime, the time it takes to do a test, etc. and gives a reasonable(within 5%) answer as to where time would probably be best spent in the project at that time.

In the Seventeen or Bust forum(SOB is related to the Sierpenski problem) people keep claiming sieving is way behind in efficiency, but since the main goal is to find the last 10(?) primes I'm not certain this is true.

Known statistics(for Seventeen or Bust):

-approximately 15 values sieved for every 1,000 billion
-about 45 billion numbers processed in a 24 hour period on an average computer(this is a fairly wild guess based on my opinion of what an "average" computer amounts to)
-an actual primality test takes about 8.68 days(12,500 minutes)
-the odds of a number x being prime 1/log x

I'm sure I'm about to hate the limited editing feature in these forums.

[url=http://www.seventeenorbust.com/stats/]LInk to SOB stats.[/url]

[QUOTE]n the Seventeen or Bust forum(SOB is related to the Sierpenski problem) people keep claiming sieving is way behind in efficiency, but since the main goal is to find the last 10(?) primes I'm not certain this is true.
[/QUOTE]

The problem with SOB is that the search is open-ended. They will probably never solve it because the last few numbers to be found will be very, very large. This means they can sieve 'til the cows come home and they will not have done enough. Sure finding a prime will eliminate a number and sieving efficiency will go up. Imagine they know the last number is about 100 million digits and each test takes over ten years on current hardware, they'll need to sieve extremely deeply indeed to save time.

SOB have done a great job finding big primes that partially solve the S-problem but I am not holding my breath for the complete solution :evil:

[QUOTE=paulunderwood]The problem with SOB is that the search is open-ended. They will probably never solve it because the last few numbers to be found will be very, very large. This means they can sieve 'til the cows come home and they will not have done enough. Sure finding a prime will eliminate a number and sieving efficiency will go up. Imagine they know the last number is about 100 million digits and each test takes over ten years on current hardware, they'll need to sieve extremely deeply indeed to save time.

SOB have done a great job finding big primes that partially solve the S-problem but I am not holding my breath for the complete solution :evil:[/QUOTE]

Bold claims. Please give some mathematical justification for them.

In fact, *if* a prime does exist for each multiplier, then the problem
is not "open-ended". It is definitely finite in duration. Of course, if a prime
doesn't exists for one (or more) multiplier, then of course the project
is open ended.

I expect that a prime under 10M digits will be found for each multiplier.
Maybe 1 multiplier will require over 10M.

Following Sam Wagstaff's heuristic for Mersenne primes gives better
than a 50% chance that k*2^n + 1 WILL have a prime for M < n < 2M
for large M. The current bound is M ~ 1.3M. 8 times this bound is ~ 10M.
The (very rough) probability that a prime will not be found less than 10M
is less than (1/2)^3 for each K. There are 9 remaining candidates.
(For Mersenne primes, the probability is roughly .56)

Determining the probability that k*2^n + 1 is prime for some n between
M and 2M would be an interesting exercize. (heuristic, not proof)

I agree that this is a VERY rough analysis. But it is better than just
"I have a feeling".

[QUOTE=R.D. Silverman]In fact, *if* a prime does exist for each multiplier, then the problem is not "open-ended". It is definitely finite in duration. Of course, if a prime doesn't exists for one (or more) multiplier, then of course the project is open ended.[/QUOTE]

That's not right. Suppose that the last prime occurs for an exponent about 10^10 (which is highly possible). If computer hardware does not advance enough to attack exponents in this range, nobody will be able to find this prime. So the problem will remain open forever, even if the search range is finite.

[QUOTE=R.D. Silverman]I expect that a prime under 10M digits will be found for each multiplier.
Maybe 1 multiplier will require over 10M.[/QUOTE]
From current trends (using extrapolation), *several* multipliers will require exponents above 10^7. See [url]http://www.mersenneforum.org/showthread.php?t=5630[/url] for a thread where Bob failed completely to predict the number of terms of a sequence.

[QUOTE=R.D. Silverman]Following Sam Wagstaff's heuristic for Mersenne primes gives better
than a 50% chance that k*2^n + 1 WILL have a prime for M < n < 2M
for large M. The current bound is M ~ 1.3M. 8 times this bound is ~ 10M.
The (very rough) probability that a prime will not be found less than 10M
is less than (1/2)^3 for each K. There are 9 remaining candidates.
(For Mersenne primes, the probability is roughly .56)[/QUOTE]
According to [url]http://www.seventeenorbust.com/stats/[/url] the actual exponents being tested are between 9M and 10M, so the numbers have about 3,000,000 digits.

[QUOTE=alpertron]That's not right. Suppose that the last prime occurs for an exponent about 10^10 (which is highly possible). If computer hardware does not advance enough to attack exponents in this range, nobody will be able to find this prime. So the problem will remain open forever, even if the search range is finite.


From current trends (using extrapolation), *several* multipliers will require exponents above 10^7. See [url]http://www.mersenneforum.org/showthread.php?t=5630[/url] for a thread where Bob failed completely to predict the number of terms of a sequence.[/QUOTE]

"failed completely to predict". And you know this how?

In fact, I did not predict the number of terms. I only said that I had
a heuristic that suggests infinitely many. I did *not* predict the
sequence density. So your claim "failed to predict number of terms"
is complete nonsense. Indeed, I have seen no mathematics that
predicts the number of such pairs is finite. We've only seen some
limited computation. and 2^62 is a LONG way from oo.

If you think I am wrong I would be very happy to hear your
mathematical reasoning.

A (moderately straightforward) application of the "large sieve" shows
that for any integer D, we should have x and x+D with the same
number of prime factors (indeed the same number of total factors)
infinitely often.

{This was a *theorem* in the dissertation of my ex}
The *number* of factors is not *bounded* by the theorem. [this is
important]

Now, when D is small relative to x (D = 1 is small) then if x is smooth
infinitely often (and there are infinitely many smooth numbers by direct
construction} then x+D should have the same number of factors as x
infinitely often. If x has enough factors to be smooth (~log (x) factors)
then so will x + D since log(x) ~ log(x + D) unless D is large.

Note that such pairs become very SCARSE. As John Selfridge said:
we know loglog x goes to inifinity, but noone has ever seen it do so.

If the number of pairs (x, x+1) < M that are smooth grows as loglog M
(or worse!) then finding them will be hard indeed.

This heuristic may be wrong. But is it a lot better than the "compute first,
and think about the mathematics later" approach already taken by
people in this group.

Apply some *reasoning* BEFORE you compute. I could be very wrong.
My heuristic might be wrong. But I at least applied some reasoning to the
problem. You have shown NONE.

Citing a simpler example, heuristics say that the set of pairs (p, p+D) where both p and p+D is prime should be infinite (by adding probabilities for individual pairs), but when D is odd there is only one pair (p=2).

Maybe your heuristic work for the majority of values of D, but not for particular values, such as D=1 in our case. This shows that some computing is necessary to avoid gross errors.

[QUOTE=R.D. Silverman]I expect that a prime under 10M digits will be found for each multiplier.
Maybe 1 multiplier will require over 10M.[/quote]

William Lipp created a prediction model - unfortunately, I only find his [url=http://www.free-dc.org/forum/showpost.php?p=66799&postcount=3]predictions[/url], not the model itself.
So far, the predictions were not that bad. According to that model, it is unlikely that there are more than 2 more primes below 10M digits.

But I welcome every heuristic that indicates an ealier finish. :wink:


[quote]There are 9 remaining candidates.[/QUOTE]

Since last december: 8 :smile:

[QUOTE=Mystwalker]William Lipp created a prediction model - unfortunately, I only find his [url=http://www.free-dc.org/forum/showpost.php?p=66799&postcount=3]predictions[/url], not the model itself.
So far, the predictions were not that bad. According to that model, it is unlikely that there are more than 2 more primes below 10M digits.

But I welcome every heuristic that indicates an ealier finish. :wink:




Since last december: 8 :smile:[/QUOTE]

I am (VERY VERY!) guilty of a cognitive error. The SoB web page shows
current test limits of ~13 million. I had either misread or mentally
translated that into 1.3 million.

I do expect that the remaining primes (with perhaps 1 exception) will
be found within 3 more doublings of the current lower limit test bound.
I think the smallest untested n is about 5 million (??) which means
testing n to 40 million (12 million digits; 40 log_10(2) ~ 12)

[QUOTE]Bold claims. Please give some mathematical justification for them.[/QUOTE]

I have, personally, no mathematical reasoning for this. Rather, I rely on greater minds to do the predictions.

[QUOTE]n fact, *if* a prime does exist for each multiplier, then the problem
is not "open-ended". It is definitely finite in duration. Of course, if a prime
doesn't exists for one (or more) multiplier, then of course the project
is open ended.[/QUOTE]

I really meant that the limit to which sieving should be done is "undetermined" because the primes to be found to solve the S-problem have an unknown size. For efficiency does SOB sieve for (last) exponent (of 2) to 40 million (Silverman) or 18 trillion (Lipp) :question:

[QUOTE]Following Sam Wagstaff's heuristic for Mersenne primes gives better
than a 50% chance that k*2^n + 1 WILL have a prime for M < n < 2M[/QUOTE]

This is okay for Mersenne primes, but for the Sierpinski primes the "weights" are much lower.

For 321, I predict a prime at 1.33 times the size of the previous one. How? By plugging known 321 prime exponents into a spreadsheet and getting it to work out the average factor increase.

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: [URL="http://www.rieselsieve.com/forum/viewtopic.php?t=650"]http://www.rieselsieve.com/forum/viewtopic.php?t=650[/URL]

[QUOTE=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: [URL="http://www.rieselsieve.com/forum/viewtopic.php?t=650"]http:/www.rieselsieve.com/forum/viewtopic.php?t=650[/URL][/QUOTE]


Please say something about HOW you arrived at these numbers.

[QUOTE=R.D. Silverman]Please say something about HOW you arrived at these numbers.[/QUOTE]

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.

[QUOTE=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.
[/QUOTE]

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:
[url]http://www.seventeenorbust.com/stats/rangeStatsEx.mhtml[/url]

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)

[url=http://www.free-dc.org/forum/showthread.php?t=10313]Here's the thread[/url], for those interested, although I made some rather embarrassing false starts.

[QUOTE=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.

[/QUOTE]

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.

[QUOTE=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.[/QUOTE]
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.

Btw, the second paragraph is tongue in cheek.