What happens next?

[cjohnsto]

I was wondering what we are going to do when we run out of k values?
Sure it may be a year (or longer) off but you never know when it will happen so i suggest we plan. I have seen suggestions to change over to the Reisel problem when this is finished and I agree since the only real difference is whether you add or subtract one from the number. So it should be fairly easy to change the code to deal with these numbers.
What do people think?

And don't say we wont have to worry about that for ages because it is better to be prepared. And Personally wouldn't mind if we were doing both Sierpinski and the Reisel problems at the same time.
<math politics>Also unlike the Sierpinski problem there are lots of unclaimed k values.</math politics>

Craig.

[Joe O]

Originally posted by cjohnsto
I was wondering what we are going to do when we run out of k values?
I have seen suggestions to change over to the Reisel problem when this is finished and I agree since the only real difference is whether you add or subtract one from the number. So it should be fairly easy to change the code to deal with these numbers.
What do people think?
<math politics>Also unlike the Sierpinski problem there are lots of unclaimed k values.</math politics>

Craig.

I guess 35 unclaimed K values for the Reisel problem is a "lot".
It seems there are currently 112 k values for which no prime has been found:

Values of k to be searched for n > 524288
k nmax tested Current searcher
2293 524400 Eugen Muischnek
23669 525000
26773 525000
38473 576000 Ray Ballinger
40597 524288 Brian Beesley
46663 573000 Ray Ballinger
67117 591700 Eugen Muischnek
71009 524288 Brian Beesley
81041 525000
93997 525000
97139 525000
103259 610200 Olivier Haeberlé
107347 551290 Olivier Haeberlé
109897 572100 Olivier Haeberlé
110413 692800 Olivier Haeberlé
114487 524288 Olivier Haeberlé
123547 524288
126667 525000 Ray Ballinger
141941 524288
143047 524288
149797 525000
150847 525000
152713 525000 Ray Ballinger
161669 620330 Richard Heylen
162941 700000 Chris Florin
191249 525000
192089 524288
192971 528000 Daniel Papp
196597 575800
204223 667200 Olivier Haeberlé
206039 743100 Olivier Haeberlé
206231 725500 Olivier Haeberlé
212893 524288 David Anderson
215443 636000 Olivier Haeberlé
215503 595800 Olivier Haeberlé
220033 605100 Olivier Haeberlé
226153 615000 Olivier Haeberlé
245561 760000 Dale Andrews
250027 524288 Kevin O'Hare
252191 580000 Steve Scott
304207 637000 Eugen Muischnek
309817 525000
319511 525000
324011 525000 Ray Ballinger
325123 526000
325627 558240
342847 760000 Dale Andrews
327671 567000 Jeff Wolfe
345067 524288
357659 524300 Nuutti Kuosa
363343 525000
409753 530950 Kevin O'Hare
415267 525000 Anton Oleynick
417643 525000
444637 760000 Dale Andrews
467917 803900 Olivier Haeberlé
469949 642900
470173 691100 Olivier Haeberlé
474491 617100 Olivier Haeberlé
485557 884600 Olivier Haeberlé
485767 563300 Olivier Haeberlé
494743 854300 Olivier Haeberlé
500621 601900 Olivier Haeberlé



Values of k to be searched for n > 262144
k nmax tested Current searcher
659 350000 Janusz Szmidt
9221 262144 Richard Heylen
31859 262500 Lev Semenets
65531 279000 Andres Aitsen
74699 450000 Patrick Pirson
89707 262144 Richard Heylen
93839 273800 Richard Kapek
113983 350000 Tom Kuechler
121889 400000 Tom Kuechler
129007 348000 Peter Shaw
146561 502000 Steven Harvey
170591 324400
201193 302000
234343 300000 Anonymous
234847 350000 Janusz Szmidt
235601 262144 Andres Aitsen
246299 300000 Janusz Szmidt
261221 501500 Kevin O'Hare
273809 277350
275293 360000 David Kokales
279703 350000 Janusz Szmidt
315929 310000 Janusz Szmidt
336839 300000 Anonymous
342673 451500 Dave Linton
344759 302000
350107 264800 Jeff Wolfe
353159 520800 Kevin O'Hare
357491 267400
362609 265000
364903 375000 Tom Kuechler
365159 262144 David Anderson
368411 265000 Reto Keiser
371893 373000 Peter Shaw
382691 292940 Reserved
384539 300000 Helmut Zeisel
386801 270000
397027 400000 Nuutti Kuosa
398023 469000 Ray Ballinger
401143 280600 Torbjörn Alm
401617 400000 Dave Linton
402539 300000
412717 263800 Nuutti Kuosa
416413 314470
428639 328700
450457 263000 Marcin Lipinski
458743 282600 Olivier Haeberlé
460139 262144 Daniel Papp
465869 262144 Richard Heylen
477583 400100 Olivier Haeberlé
502541 519500 Olivier Haeberlé
502573 400000 Nuutti Kuosa
504613 468000 Helmut Zeisel

from the following status page. (http://www.prothsearch.net/rieselsearch.html)

[jwolfe]

There are currently 115 k's left in the Riesel search (52 for n < 524288 and 63 for n >= 524288). The unclaimed k's you list from the status page do not include k's reserved on this page (http://www.prothsearch.net/rieselbook.html) but not yet reflected on the status page.

- Jeff

[Pascal]

Another question: What happens to a block that was seeded out but no results returned?

Will you seed them again and if, when?

[Vato]

I assume that when a prime has been found. that when it is tested for primailty, that a twin prime test is being run in parallel, or immediately afterwards?

Also, are all values of n that are still outstanding, below the one which generated the prime, waited for? Are the ones that time out reissued? ie. do we claim that ALL values of n below the magic one have been tested (assuming correct operation of everyones computer)? I'm dumb but I assume this is the Keller Prime bit.

Given these, I would assume we have plenty of work ahead of us with the remaining 14, and the Riesel problem.... I also would not object to us starting this prior to completion of the Serpienski problem - ie go and pick up some of the currently unreserved blocks and start handing them out when we only have 4 or 5 k values to go on the current project...

[Mystwalker]

Another question: What happens to a block that was seeded out but no results returned?

Generally, when the server doesn't get a sign of life (signal that a block has been processed) within 2 weeks, the n value gets reassigned and the Client gets a new value once he connects.


Given these, I would assume we have plenty of work ahead of us with the remaining 14, and the Riesel problem.... I also would not object to us starting this prior to completion of the Serpienski problem - ie go and pick up some of the currently unreserved blocks and start handing them out when we only have 4 or 5 k values to go on the current project...

I concur. The most work are not the k's we find primes for, but those we don't. With k = 27653, we have searched almost all n values < 3M, and those values mean ~10x work time than those other k/n pairs that are computed ATM - and maybe 20x more than n values < 600,000. These are of course rough estimations, but I think you get the point.

Asuming one of the remaining k's is a Sierpinski number, we would have infinite work to do the way the project is designed. AFAIK when we hit n = 10M, it's very likely it's a Sierpinski number. But that will nonetheless take a lot of time! So we should be grateful for every k value sorted out this early - and every prime hitting the TOP30 and gaining many more members! :D

So keep on crunching! :cheers:

[smh]

AFAIK when we hit n = 10M, it's very likely it's a Sierpinski number.

No it's not. It's very likely that none of the 14 remaining values is a Sierpinskie number.

According to http://groups.yahoo.com/group/primenumbers/message/878 the chances of solving the problem with all N's below 10M (10^7) is about 0.000263 %

Now this calculation was made when there were 19 K values left so it might be a bit higer now, but the chance to solve the problem before all K's reach 10M is way, way less then 1%

[Joe O]

Jeff, I see what you mean. Combining the two pages I get:

k nmax tested
74699 450000
93997 525000
97139 525000
141941 524288
143047 524288
149797 525000
150847 525000
170591 324400 <<May Be Reserved!
191249 525000
192089 524288
196597 575800
309817 525000
319511 525000
325123 526000
325627 558240
345067 524288
363343 525000
371893 373000
417643 525000
428639 328700
469949 642900

That is 20 unreserved values and one questionable.

PS I have this all in an Excel spreadsheet if anyone is interested.

[jjjjL]

Originally posted by smh

According to http://groups.yahoo.com/group/primenumbers/message/878the chances of solving the problem with all N's below 10M (10^7) is about 0.000263 %

Now this calculation was made when there were 19 K values left so it might be a bit higer now, but the chance to solve the problem before all K's reach 10M is way, way less then 1%

you know, i've seen that page before. i always knew that the formula he was using was bad but i didn't have the data to prove it. now we do. just for fun, i tried using his formula with the 14 remaining k's instead of the 19 that he made his "prediction" with? all of the sudden, we get this:


N : 10^7 --> chance to solve : 0.0013662
N : 10^8 --> chance to solve : 0.084388
N : 10^9 --> chance to solve : 0.31669
N : 10^10 --> chance to solve : 0.54922
N : 10^11 --> chance to solve : 0.7166
N : 10^12 --> chance to solve : 0.82494
N : 10^13 --> chance to solve : 0.89251
N : 10^14 --> chance to solve : 0.9341
N : 10^15 --> chance to solve : 0.95956
N : 10^16 --> chance to solve : 0.97515
N : 10^17 --> chance to solve : 0.9847
N : 10^18 --> chance to solve : 0.99057
N : 10^19 --> chance to solve : 0.99417
N : 10^20 --> chance to solve : 0.99639
N : 10^25 --> chance to solve : 0.99967
N : 10^30 --> chance to solve : 0.99997

for those of you that haven't bothered to follow the link, here's the original:

N : 10^7 --> chance to solve : 0.00000263
N : 10^8 --> chance to solve : 0.000949
N : 10^9 --> chance to solve : 0.0151
N : 10^10 --> chance to solve : 0.0681
N : 10^11 --> chance to solve : 0.166
N : 10^12 --> chance to solve : 0.291
N : 10^13 --> chance to solve : 0.420
N : 10^14 --> chance to solve : 0.538
N : 10^15 --> chance to solve : 0.639
N : 10^16 --> chance to solve : 0.720
N : 10^17 --> chance to solve : 0.785
N : 10^18 --> chance to solve : 0.836
N : 10^19 --> chance to solve : 0.875
N : 10^20 --> chance to solve : 0.905
N : 10^25 --> chance to solve : 0.976
N : 10^30 --> chance to solve : 0.994

I especially like how the chance of solving the Sierpinski problem has suddenly increased 1000x times over for 10^8 and has increased from under 2% to over 30% for 10^9. What does this tell us? Did the chances of solving the Seirpinski problem really increase that much just because we found a few primes? NO! The formula is wrong. I promise you, when the next prime is found, it will also show that our chances have "increased" again just like they did for each of the 3 we have found so far. In other words, the assumptions made in contructing the formula made to produce these predictions has a fundamental flaw. I've always known it was wrong, i'm just glad i can prove in now that we have more data.

for those interested in redoing my calculations, here is the matlab script i wrote to use his formula. the only simplifying assumption i made was that the current limit we have searched all remaining numbers to was 1M. Even if you change it to 2M, it still makes only a small diference. Correct it if you like... the point is it really doesn't matter how good the numbers you plug into this formula are, it will never be right.

----
w = [.2,.25,.23,.08,.19,.07,.2,.12,.11,.19,.28,.25,.07,.18];
n = 1000000;
for N = 7:30

z = 1;

for i = 1:14
y = 1-exp(-w(i)*log(10^N/n)/log(2)*2);
z = y * z;
end

U(N) = z;

end
---



also, don't know if it's a real journal article or what but there's this paper written by Yves Gallot and the copy i have is just called weight.pdf. Anyway, that paper has a more complex equation that's also supposed to predict when the Seirpinski problem will be solved. i have tried to redo his calculations but it appears that he may have done his original calculations incorrectly even with his own equations so I'll have to have some other people help me. I was under the impression that Yves was an ok mathematcian and that most of his failings had to do with his use of the English language ;). joking aside, even if his tables are right, his equations suffer from the same deficiency that these ones do. the probablities "improve" every time a new value is discovered. i don't want to trash Yves too much... his paper is a nice attempt. if you read the whole thing, he does make all kinds of caveats like "our knowledge on these kinds of predictions is zero" and "i have no reason to believe this equation other than it seems to fit data." opps... data just changed... time to refit your equation ;)

so yeah, don't waste your time reading these estimates. they are wrong.

-Louie

[smh]

Thats sure put things in a different perspect.

I don't know anything about the math behind it, but i guess you are probably right if you say there's a flaw in that formula.

Just thought that Yves and Jack are knowladgeble people if it comes to primes, and who am i to say they are wrong ;)

I guess you're not going to bring this up on the primenumbers mailing list ;)


One thing they are probably right in:
It's hard to solve the problem, even if we have to search only to 10^8

[Joe O]

I think I have to take exception with you. I think that it is "alright" that the probabilities change when more data is available.
Look at the "birthday problem". When you put 23 people in a room the probability is 0.507297 that 2 people have the same birthday. But if you have 22 people in a room with different birthdays, the probability that the next person walking in to the room has a matching birthday is only 0.492703 (or is it 0.46165 ? I don't remember). In any case, once you have n people with distinct birthdays, the probability of the next person's birthday matching one of them is less than the a priori probability of n+1 people having 2 or more people with a birthday in common.

[jjjjL]

i'm familar with the birthday problem. explain to me how that has anything to do with this.

-Louie

[Joe O]

As the first example I could think of where having "new/more" data changed the computed probabilities.

Perhaps the following analysis would better illustrate the problem. If the probability of finding a prime for a given K in a given range N is of the order 10^-1 then the probability of finding a prime for 2 Ks in that range is ~ 10^-2, 3 is ~ 10^-3 etc. Specifically the probability of finding 14 primes would be ~ 10^-14 and 19 primes ~ 10^-19. So finding 14 primes instead of 19 primes would be 100000 times more likely.

[Kosmaj]

There was one more related message (http://groups.yahoo.com/group/primenumbers/message/10185) on PrimeNumbers with a prediction that looks reasonable and easy to understand.


From: "David Broadhurst" <d.broadhurst@o...>
Date: Wed Dec 4, 2002 5:12 pm
Subject: Fifteen or Bust

Also congrats to Yves, whose heuristic goes from
15.7 remaining down to 12.8 remaining when the
upper limit on n goes from 2^19 up to 2^20.
So with all those new users we may get to ToB soon.
The B is very likely to outlive me, but
it's still fun seeing the first letter change.
Yves estimates that the next time the
initial letter might change from S to F
may be between n=2^24 and n=2^25,

[Firebirth]

Why on earth do you make probability by induction instead of using (what we know so far about) pi(x)?

[philmoore]

I've been trying to understand both Yves Gallot's predictions and Louie's computation based on his formulas - It's not clear to me how discovering 3 new primes has suddenly reduced the N-value that gives us a 50% chance of solving the problem (according to Gallot) from just under 10^14 to now just under 10^10. Louie's claim is that the formula is wrong, and that the next discovery will reduce this value even further. I decided to take a simple-minded approach: I graphed the data on an Excel spreadsheet. I tried to attach it to send it to this forum but was informed that .xls was not an acceptable extent for attachments. Therefore, if anyone is interested, here is the Excel data which you can paste into your own copy of Excel to do a scatter plot:

0 15.261
1 14.968
2 14.415
3 13.582
4 12.549
5 11.525
6 10.553
7 9.674
8 8.925
9 8.185
10 7.468
11 7.022
12 6.585
13 6.129
14 5.883
15 5.358
16 4.858
17 4.585
18 4.248
19 4.087
20 3.807

For each value of m from 1 to 20, I graphed the base-2 logarithm of the number of remaining Sierpinski candidates when all n have been searched up to 2^m. (I assume that the data for m=20 is complete, i.e., all Keller primes for n<1048576 have already been found.) Basically, this is a log-log plot where a power law distribution would be revealed if the data fall on a straight line. As you can see if you do the graph, the curve is not straight. If anything, the data from n=3 to n=20 looks concave up, but it also looks like the concavity is decreasing. If you look at just the data from m=10 to m=20, the curve isn't too far from a straight line. So where does this line cross the x-axis? I've tried various fits and come up with about 34, i.e. at n=2^34, the number of remaining candidates should be "about" 2^0=1. To give ourselves a 50% chance of solving the problem, we should set the number of remaining candidates to be 1/2, i.e., y should be -1 instead of 0. Then we get a prediction of around n=2^36 or so, or about 7*10^10. Of course, these are just rough estimates, and if Louie is right, we should see some sort of change in concavity in the graph with the next few discoveries. (Perhaps we already see a suggestion of that in the data for n=18 to n=20.) If anyone is interested, we could get a more complete picture of the behavior by including the data for all known Keller primes with k<78557, but I would be surprised if this shows any trends that are not apparent in this simplified version. At any rate, I don't think we have to worry about the project running out of work in the near future, but it will be interesting to see what unfolds!

Phil

[nuutti]

There are speculation about mersennes here :
http://www.utm.edu/research/primes/notes/faq/NextMersenne.html

and according to my knowledge Yves Gallot has forecasted that there will be 2.9 primes between 2^19 = 524,288 and 2^20 = 1,048,576 and we have found 3 so his forecast can't be so bad.

Here is my mail / question about his paper to primenumbers mailing list :
http://groups.yahoo.com/group/primenumbers/message/10254

Yours,

Nuutti

[philmoore]

Thanks, Nuuti - I've been studying the predictions some more, and think I'm starting to understand why the situation looks so much more hopeful now that we are down to 14 candidates. Gallot's formulas take into account the Proth weight of each candidate. The Proth weight is, roughly speaking, a measure of how many candidates will not be removed by sieving. k=78,557 is the first number with a Proth weight of zero, meaning that all prime candidates will be removed by sieving, i.e., 78,557 is a Sierpinski number. Computing the Proth weights of the original 17 candidates at the web site:
http://www.brennen.net/primes/ProthWeight.htmlwe get the following table:

4847 .09877
5359 .11761
10223 .11875
19249 .04339
21181 .09649
22699 .04054
24737 .09820
27653 .06394
28433 .05424
33661 .09592
44131 .14273 (eliminated)
46157 .05424 (eliminated)
54767 .12846
55459 .14102
65567 .04567 (eliminated)
67607 .03540
69109 .08906

The smaller the Proth weight, the more work we expect to have to do on average to eliminate the exponent. Looking at Gallot's formulas again, I can see that eliminating the most recent exponent 44131 with the highest of the seventeen Proth weights didn't do nearly as much for improving the predictions as did eliminating the two low Proth weight numbers 46157 and 65567. If instead of these two, we had eliminated 54767 and 55459, the prediction would not have improved nearly as dramatically.

We can consider the above seventeen values to fall into two distinct groupings: the 10 values all greater than .089 and the 7 values all less than .064. The first 10 should be easier to eliminate, but we were lucky in that two of the three eliminations found so far fall in the second group.

Let's hope for a couple more lucky finds!

[philmoore]

A note from Jack Brennen on the primenumbers newsgroup:
http://groups.yahoo.com/group/primenumbers/message/10258
Jack wrote the Proth weight applet referred to in the post directly above this one, and he claims that there is a factor of 2 discrepancy in the Proth weights Louie used in the formula above. He says that when the correct weights are used, the new predictions for solution of the Sierpinski problem are a little better, but not dramatically better, with a 50% chance to solve with an n-value closer to 10^13 than 10^14. This is still significantly larger than my simple-minded linear analysis above, which gave a guess of 7*10^10. If Jack Brennan is correct, the graph should continue to display an overall shape of concave up, while as I mentioned above, Louie's claim means that the concavity should change. Within a few months, we should have the data to see which claim is correct!

[jjjjL]

if what Jack says is true, i appologize for being overly harsh of his analysis. for some reason the ProthWeight applet linked to in his post didn't work for me so I used the weights i found published w/o realizing they were different. my mistake, sorry. i still think his equation may make too many simplifying assumptions but i will admit that there is good reason to believe his equation is the in the ballpark.

-Louie

[nuutti]

Well. When we have checked up to 2,100,00 we will have more results / data and we will able to do more accurate predictions about these forecasts.

Yours,

Nuutti

[Mystwalker]

Another one - with a medium Proth weight. I guess that won't change chances that much, will it?

[smh]

for some reason the ProthWeight applet linked to in his post didn't work for me

Do you happen to run Windows XP on the pc you tried to use the applet? In that case, installing Service Pack 1 might solve your problem. You can also download the Java Virtual Machine from the SUN website.

[R. Gerbicz]

you know, i've seen that page before. i always knew that the formula he was using was bad but i didn't have the data to prove it. now we do.
-Louie

Interesting. I've figured out a formula, that's I think is correct, the posted numbers are correct in the yahoo forum. But the formula is correct only if you divide the weights by 2. Probably there are two different definitions for weights, I don't know the reason for this.

I've precomputed the weights for k values, to get this I've sieved the remaining 8 values for 0<n<50M up to p=10M.
This is the "a" vector. Then w=a/(50M*d) is the weight. T(n) is the probability that we will complete seventeenorbust project before n, assuming that we've not missed primes up to n=10M.

default(primelimit,10^7)
a=[387230,141142,329397,134875,347832,329159,464292,116978];\
d=1.0;forprime(p=2,10^7,d*=(1-1/p));\
w=a/(50000000*d)
T(n)=prod(i=1,8,1-exp(-w[i]/log(2)*log(n/10^7)))

By

for(i=8,25,print("T(10^",i,")=",T(10^i)))

I've gotten:

T(10^8)=0.0003464
T(10^9)=0.01451
T(10^10)=0.07478
T(10^11)=0.1807
T(10^12)=0.3059
T(10^13)=0.4280
T(10^14)=0.5364
T(10^15)=0.6279
T(10^16)=0.7031
T(10^17)=0.7641
T(10^18)=0.8131
T(10^19)=0.8523
T(10^20)=0.8834
T(10^21)=0.9081
T(10^22)=0.9276
T(10^23)=0.9430
T(10^24)=0.9552
T(10^25)=0.9647

By about 0.495 probability we'll complete the project before n=4*10^13.

[nuutti]

Yes, but in the last phase we will have only one k left and it is highly composite so not very many numbers to prp test.

I have to say that this is quite much about luck.


Nuutti

[R. Gerbicz]

Yes, but in the last phase we will have only one k left and it is highly composite so not very many numbers to prp test.
I have to say that this is quite much about luck.
Nuutti

Yes, if we've luck then we can complete the project before n=4*10^13.

I've computed the expected n, when we'll find a prime by 50% probability, if all numbers tested up to 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

So yes the last step is very-very critical because in average we'll reach remaining=1 at about 3.1*10^9 but we'll eliminate this at 4.5*10^13.