Discussion about CPU time needed and k's remaining

[KEP]

@ Gary:

I might not be getting quite what you say as you've needly stated...

Regarding Base 19, there is approximately 3,850,000 candidates remaining for 1540 (should be reduced to 1538) k's remaining. Since I'm not using LLR, but only test the presieved range using OpenPFGW, it's hard for me to give you an exact timing, but for you my friend, here is a timing for Base 19 at n=64000 for k=2526 it is 1.596 ms per iteration or ~434 sec. For base 19 at n=100000 for k=736986 it is 2.626 ms per iteration or ~1116 sec.

Since I'm testing only using WinPFGW, many testings will be saved and therefor a lot of time will be saved and I'm going to put 4 cores on the sieved file, which has been sieved to ~25G using srsieve. It was sieved to that level in just 14 days or so. But given the upper timings, feel free to express your oppinion to me and let me know what you feel about my future plans.

I think for now, that I'll wrap the base 3 on my dual core, and work 24/7 on my quad core on the base 19 after that I might consider sieving a bit further before releasing the presieved files for the bases 22 and 23. It really needs a lot of sieving before its optimal to do LLR for these bases, so I think it will be there that my focus will be put once I complete the base 19. Maybe if it isn't wrapped at n<=100K I may consider to do an even higher n search and just hand over the sieve files for the bases 22 and 23 for later use (maybe even for llrnet)...

KEP!

[gd_barnes]

Originally Posted by KEP

@ Gary:

I might not be getting quite what you say as you've needly stated...

Regarding Base 19, there is approximately 3,850,000 candidates remaining for 1540 (should be reduced to 1538) k's remaining. Since I'm not using LLR, but only test the presieved range using OpenPFGW, it's hard for me to give you an exact timing, but for you my friend, here is a timing for Base 19 at n=64000 for k=2526 it is 1.596 ms per iteration or ~434 sec. For base 19 at n=100000 for k=736986 it is 2.626 ms per iteration or ~1116 sec.

Since I'm testing only using WinPFGW, many testings will be saved and therefor a lot of time will be saved and I'm going to put 4 cores on the sieved file, which has been sieved to ~25G using srsieve. It was sieved to that level in just 14 days or so. But given the upper timings, feel free to express your oppinion to me and let me know what you feel about my future plans.

I think for now, that I'll wrap the base 3 on my dual core, and work 24/7 on my quad core on the base 19 after that I might consider sieving a bit further before releasing the presieved files for the bases 22 and 23. It really needs a lot of sieving before its optimal to do LLR for these bases, so I think it will be there that my focus will be put once I complete the base 19. Maybe if it isn't wrapped at n<=100K I may consider to do an even higher n search and just hand over the sieve files for the bases 22 and 23 for later use (maybe even for llrnet)...

KEP!

LLR is faster than PFGW in most cases for pure primality testing. The only thing it won't do is automatically remove k-values for you when a prime is found for them. Personally, I use LLR and manually remove the k's with primes using srfile from my sieved file about every n=2-5K depending on how high the n-range is and how many k's are found with primes.

OK, now I can give you a good idea of how long Sierp base 19 to n=100K should take. Here is what we have:

3.85M candidates remaining to test in your sieved file

434 secs. avg. time / candidate (60% of n-range gives a good average testing time over the entire n-range due to the exponential increase in testing times as n's become greater.)

Reduce total time by ~25% to allow for tests not needed on k's where primes are found. (I think that is too high of a reduction but I'll give it the benefit of the doubt here.)

So:

3.85M * 434 * (1 - .25) = 1.253G CPU secs. = 14504 CPU days = 39.7 CPU years!!

Oh my goodness, I well UNDER estimated the resources needed for this! If you have 4 cores of a quad running non-stop 24x7, it will still take you 39.7 / 4 = ~10 years to complete it!!

I may be missing something here because that seems too high but even if I've over-estimated 10-FOLD, 1 calender year utilizing a quad 24x7 is far longer than 4-6 weeks!

The above said, I've used this method before and have never been off more than 2 times, i.e. estimate of 20 days vs. actual of 10 days or 40 days.

The issue is the number of candidates for so many k's. That's what I think you're missing. One other thing I think you're missing: You used the phrase "Maybe if it isn't wrapped at n<=100K" which tells me that you think that Sierp base 19 has a good chance of having all of it's k's found with primes by n=100K. Let me put it this way, there's not a snowball chance in heck that all k-values will have primes by n=100M (1000x n=100K)!! At n=100K, you're likely to still have 500-750 k's remaining! Those k's will not drop like base 3. I'll put it another way, I would wager my last dollar that we will not be able to prove either base 19 in any of our lifetimes nor our children's lifetimes even with a doubling of CPU speed every 2 years unless there is a new way found to search for primes! It's likely to need searching to n=1T or higher!

Convinced yet? If not, test it up to n=20K and see what you think. Getting to n=25K will likely take you 4-6 weeks. Willem (Siemlink) is testing Riesel base 19 to n=30K and is already at n=25K. He should be able to give you a good idea there.


Gary

[KEP]

@Gary:

Convinced ... shure if what you state is true... however, I really think from what I've experienced yet with the Base 19, that it in fact is more prime dence than you imagine. I.e. for the first 1209 n I had 44 primes, or aproximately 1 k removed every 30 n. So I expect to have at least hundreds of primes removed at n<=20000... but it holds for the future to see....

Anyway for now I'm only planning on sieving the Bases 22 and 23...

When it comes to prove any of these conjectures in our lifetime, it all depends on weather or not Rieselsieve or Primegrid decides to take over or support our effort, but that also holds for the future to see

No matter what we believes, I'll race towards the higher n's

KEP!

[Siemelink]

Originally Posted by gd_barnes

Convinced yet? If not, test it up to n=20K and see what you think. Getting to n=25K will likely take you 4-6 weeks. Willem (Siemlink) is testing Riesel base 19 to n=30K and is already at n=25K. He should be able to give you a good idea there.

Gary

I have reserved Riesel base 19 in Februari. It started with 4500 candidates. After 5 months I am on 1500 candidates at n = 29,000. My effort has usually been 5 or six cores. Nowadays I find about 1 prime per day.
These sort of searches won't have a hope of closing until BOINC gets interested. So I pace myself. I set a target that is determined by my resources, not so much by the project.
I am amazed by Masser, who has been searching some base 5s for years now.

So many projects, so little cores!

Willem

[michaf]

Originally Posted by Siemelink

I have reserved Riesel base 19 in Februari. It started with 4500 candidates. After 5 months I am on 1500 candidates at n = 29,000. My effort has usually been 5 or six cores. Nowadays I find about 1 prime per day.
These sort of searches won't have a hope of closing until BOINC gets interested. So I pace myself. I set a target that is determined by my resources, not so much by the project.
I am amazed by Masser, who has been searching some base 5s for years now.

So many projects, so little cores!

Willem

Even _with_ BOINC it has completely no chance of being resolved... after say n=100k, primes will come scarcely, and after 1M they will come hardly ever (See GIMPS).

Let's say that at n=100k there are 1000 k's left.
at n=1M that won't be much less then half of that, say 500k's
at n=10M 250 k's left
at n=100M 125 k's left
at n=1G 50 k's left
Needless to say, that for the time being, a test at 1G is quite a bit out of reach...

But alas, we can at least pave the roads for the people after us!

[gd_barnes]

Originally Posted by KEP

@Gary:

Convinced ... shure if what you state is true... however, I really think from what I've experienced yet with the Base 19, that it in fact is more prime dence than you imagine. I.e. for the first 1209 n I had 44 primes, or aproximately 1 k removed every 30 n. So I expect to have at least hundreds of primes removed at n<=20000... but it holds for the future to see....

Anyway for now I'm only planning on sieving the Bases 22 and 23...

When it comes to prove any of these conjectures in our lifetime, it all depends on weather or not Rieselsieve or Primegrid decides to take over or support our effort, but that also holds for the future to see

No matter what we believes, I'll race towards the higher n's

KEP!

Your experience actually proves that my estimate of k's remaining (500-700) at n=100K is almost right on!

I will provide here a crude but effective calculation that will get us to the number of k's that should be remaining for Sierp base 19 at n=100K.

For understanding purposes, I will make it easy to start with by assuming that the chance of finding a prime is the same at all n-levels, which as you see will later on, is ridiculous.


n=10K, 1612 k's remain
n=11.2K, 1539 k's remain or 73 k's removed = 73/1612 removed = 4.53%
n=12.4K, remove 4.53% of 1539 leaves 1444 k's
n=13.6K, remove 4.53% of 1444 leaves 1378 k's

and so-on-and-so-forth.

Now using a simple forumla, you're testing n=10K-100K, so 90K/1.2K = 75. So you have 75 n=1.2K ranges.

Therefore we can compute that:
1612 * (1-.0453) ^ 75 = 49 k's remaining at n=100K.

But the above is ridiculous becuase it assumes that the chance of finding a prime at each n-range never changes, so obviously the # of k's remaining is much too low.

Now to the tricky part that uses the above as a starting point but adjusts for the chance of prime at each n-level as we go:

Per the top-5000 site, the chance of prime halves as the exponent doubles while taking 4 times as long to test. Their scoring formulas prove this out by awarding 8 times the score for exponents twice as large.

Calculus would be needed to compute it exactly but here are some calculations that should be quite close. Let's let the chance of prime for n=10K-11.2K be equal to one. Now use that average of the n-range (10.6K) as a base for computing the chance of higher exponent's primes keeping in mind that the chance of prime halves as the exponent doubles. Therefore we have:

n=10K, 1612 k's remain

n=11.2K, 1539 k's remain or 73 k's removed = 73/1612 removed = 4.53% * 1 chance of prime = 4.53% removal rate

n=12.4K, using the average n-range here and the average n-range of n=10K-11.2K, the chance of prime now becomes 10.6K/11.8K =
.898. So we have 4.53% * .898 = 4.07% removal rate. So 1539 minus 4.07% leaves 1476 k's remaining.

n=13.6K, we now have a chance of prime of 10.6K/13K = .815. So we have 4.53% * .815 = 3.69% removal rate. So 1476 minus 3.69% leaves 1422 k's remaining.

Continuing this same analysis up to n=100K, I computed the following number of k's that should be remaining at respective n-levels for Sierp base 19:

n-value   k's remain
10K        1612
15K        1367
20K        1216
25K        1111
30K        1033
40K         919
50K         840
60K         781
70K         734
80K         696
90K         664
100K        636
 
and you might find this interesting:
1M          253 (only 383 removals out of 636 k's from n=100K-1M!)
10M         101 (only 152 removals out of 253 k's for n=1M-10M!!)

So my official estimate is that you will have 636 k's remaining at n=100K. As you can see, using the low n-levels is very misleading when trying to calculate time taken and k's being removed at higher n-levels.

Based on the fact that 1 - 636 / 1612 = 60.55% of all k's remaining should be eliminated between n=10K and 100K, my multiplier of reducing the testing time by 25% was probably low. It should probably be about 40%. So that reduces the estimate down from 40 CPU years to 31.8 CPU years. This is still a rough-estimate multiplier. If you assume that the chance of prime was the same at all n-levels, it would be simply 60.55% / 2 = 30.28%. But since you're eliminating more k's at the lower n-levels, reducing the testing time by something higher, without doing complex analysis, can only be an educated guess. The actual multiplier could be between 35 and 50% here but at least we have a general ball-park CPU estimate for this testing.

I have a crude spreadsheet that shows how the repetitive iterations of the formulas quickly computed this. If you'd like to see it, let me know. I don't show the n=1M and 10M calculations because it got too big.

Micha is correct that having BOINC involved will still never prove this conjecture in our lifetimes. Based on the above, I'll take it one step further: having all of the world's computers on it for the entire remaining time of mankind on Earth will not solve it! That's because, the final prime likely would have an exponent larger than 10^100! That's k*19^(10^100)+1!! That is unless we come up with a new way to compute primes.

And finally: Please don't take any of this as attempting to reduce your enthusasim for the efforts. Sometimes I can be a little terse and pointed. We need plenty of enthusiastic and passionate people such as yourself. It's only meant to inform you and amaze you at the same time.


Gary

[gd_barnes]

To whom may be interested:

I couldn't resist attempting to take the Sierp base 19 analysis above all the way to an estimate of how large the final prime will be. It simplifies things greatly to assume that there will be a 60.55% reduction in k's remaining with each power of 10 of the n-value as per my prior analysis.

Therefore we have:

n      k's remaining
10^5   636
10^6   251 (slight tweaking to prior formulas)
10^7    99 ( " " )
10^8    39
10^9    15
10^10    6.1
10^11    2.4
10^12    0.95
10^13    0.37

Therefore my estimate is that the conjecture will be proven with a final prime between n=10^12 and n=10^13. That's an exponent of somewhere between n=1 and 10 trillion!

That's certainly much less than my original estimate of n=10^100. Now, if you continue to double the speed of computers every 2 years, then I'll back off of my notion that mankind could not prove it with all of the world's computers given no new way to find primes. If you assume in 500 years that computers are 2^250 or 1.81*10^75 faster than today, then it seems very possible. But it seems unlikely that computers will continue to double in speed every 2 years into infinity and who knows, there could be some grand new technology that makes computers obsolete. So this would be open to great debate at this point on whether the conjecture could ever be proven.

As Micha said, we are paving the way for future generations.

Edit: The last thing to do would be to compute how many CPU years it would take to prove the conjecture. Needless to say, I'll leave that to others. lol


Gary

[KEP]

@Gary:

Thanks for all you info. I'm still pationated about the effort to solve the Sierpinski and Riesel conjectures. Actually I think I can be to enthutiastic from time to time untill frustration overcomes me ... however if what you state is true, we really need to get RieselSieve to help us sieve these very large ranges so we easily can remove the tons of composites not nescessary to test at all ... just out of curiosity, anyone has an ETA n value for Riesel base 2 and even Sierpinski base 2?

Regards

KEP

[gd_barnes]

Originally Posted by KEP

@Gary:

Thanks for all you info. I'm still pationated about the effort to solve the Sierpinski and Riesel conjectures. Actually I think I can be to enthutiastic from time to time untill frustration overcomes me ... however if what you state is true, we really need to get RieselSieve to help us sieve these very large ranges so we easily can remove the tons of composites not nescessary to test at all ... just out of curiosity, anyone has an ETA n value for Riesel base 2 and even Sierpinski base 2?

Regards

KEP

It's been calculated somewhere but I can't remember where. Perhaps on the Rieselsieve or SOB sites somewhere.

As Micha stated earlier, having BOINC involved won't prove many of our conjectures. I'll take that further and state that having BOINC, RieselSieve, SOB, and PrimeGrid combined involved won't prove many of our conjectures in our lifetimes and also state that many will not be proven in the next 75-100 years even with a doubling of computer speed every 2 years, which is unlikely to continue.

Sieving should be 5-10% of the total of any effort. Having them sieve is no more effective than having them LLR. It's just a matter of where we want to put our resources.

Continuing to sieve and sieve and sieve ad infinatum does not save CPU time. It wastes time. As Anon has said, RieselSieve has ranges so over-sieved, it's ridiculous. If they had used more of their resources to LLR, they'd be far further along than they are. I think that SOB has done a much better job of managing resources between sieving and LLRing.

Don't mistake constant sieving for saving total CPU time. Sure it saves LLRing time but it wastes total CPU time. Sieving to the optimal depth at varying n-range is what saves the most time overall. For instance, you mentioned sieving n=100K-1M on bases 22 and 23 to P=25T or perhaps even P=100T. That would likely be a waste of time to sieve the entire range so high. You would probably be better of sieving to P=5T-10T, break off the n=100K-150K (or n=100K-200K range), LLR it, sieve 150K-1M (or 200K-2M) to P=10T-20T, break off another range etc. Also, I think you'll find it gets very boring continually sieving for months at a time. Doing one then the other and then repeating that process is both the most interesting and the most optimal.

Niether RieselSieve nor SOB would help us solve other bases. They have way more than plenty of work as it is. BOINC and PrimeGrid would help us if you don't mind a bunch of users doing the searching that know nothing about primes. Personally, I don't like it because it removes a lot of this human interaction among people that are passionate about math or computers or primes that I generally enjoy. That's how I learn things from people who know much more than me about things.

Here I/we aim to pave the way for future projects by searching many bases to a moderate to high n-range. For instance, I think you and Micha could start a prime search project to solve the base 3 conjectures (and/or bases 7 and 15) since you both seem to enjoy base 3. I'd gladly ship one or more of those off to another project. We have plenty of work even without those. I'm not greedy. You could set up your own forum, promote things, create and update web pages, determine how things should be searched, etc. It's a lot of work but once you get it going, it's not so bad. If you ever want to consider that, I can point you in approximately the right direction and I'd certainly pitch in some cores to assist in searching on them at times.


Gary

[em99010pepe]

Originally Posted by gd_barnes

Continuing to sieve and sieve and sieve ad infinatum does not save CPU time. It wastes time. As Anon has said, RieselSieve has ranges so over-sieved, it's ridiculous. If they had used more of their resources to LLR, they'd be far further along than they are. I think that SOB has done a much better job of managing resources between sieving and LLRing.

I suggest you both some readings. Both can start by reading the sievulator manual.pdf available in the attachment at the Sievulator Thread .

[gd_barnes]

Originally Posted by em99010pepe

I suggest you both some readings. Both can start by reading the sievulator manual.pdf available in the attachment at the Sievulator Thread .

That looks interesting and I'm sure the math is very sound. But I completely disagree that RieselSieve is close to optimal sieve depth. They're so far beyond it that it's laughable at their current n-range. So be prepared as I shall no go on a long rant.

If you assume that computer speeds never increase in the future, they may be at optimal depth for an entire search to n=20M (the current top range of their sieved depth) but it's not optimum the way I or people should be looking at it.

If all you do on a 50-year project is sieve for the first 5 years and then LLR for the next 45 years, sure that might be the optimal CPU-wise for never increasing CPU speeds but it makes for both an extremely boring project and assumes no speed increases in computer resources.

That's the complaint I had at RPS. They sieve the crap out of stuff. k=5 is sieved to P=350T or more because they decided to sieve the entire range of n=470K-4M all at once and that is the most 'efficient' for n=1.3M where they are currently at. Sure, perhaps that's the most optimal CPU-wise if you're going to search all the way to 4M at today's computer speeds and you wish to find no primes for months or a year or more. That's why k=5 is only searched to n=1.3M when it should be near n=2M by now. If they would have just stopped the sieving at P=~50T, searched to n=1M, sieved to P=~100T, searched it up to about n=1.5M, sieved to P=~150T, searched to n=2M, etc., they'd be close to 2M right now. Yeah, they'd have more time to spend in the FUTURE that way, but computers will be faster in the future, and they would have saved just a little less time than that increased future time on the search up to n=2M because the removal rate at the lower n-ranges was so much less than the LLR time of those lower ranges.

RieselSieve didn't find a prime for 18 months with 66 k's remaining. That should not have happened at only n=3M with their resources but they had way too many resources dedicated to sieving under the guise of long-term efficiency. (And a lot of it had to do with issues they thought they had with the LLRnet client as I understand from Anon.) Things like that won't happen on any project that I'm moderating if I can help it.

There's more to sieving and LLRing then finding the exact optimal sieving depth that assumes static-speed CPU resources and sieving software. The 70% rule that I expouse with breaking off of n=range at powers of 2 or less times the lowest n in your range finds the best happy medium between optimum sieving efficiency, taking into account increase in future CPU-speed, and the boredom that is caused by never finding primes while sieving.

Incidentally, the 70% rule is the way that I was initially taught. I realize that better mathematical models have been found since then if you're only looking at total CPU time over several decades. But if you did that, you'd have to sieve many of our efforts to n=10M or more and sieve them into the quadrillions. (Try sieving base 19 to n=10^18 and see what the optimum would be! We'd never be searching for primes even if sr(2)sieve could sieve such a huge n-range.) After all, mathematically, that's the way to spend the least CPU time over, what, 100 years or more when we're no longer alive? That would be laughable. That's why we only chose to sieve n=100K-400K on Sierp base 6. I mean why sieve n=100K-1M when we may not even have LLR at n=400K for 4-5 years when many of us may not be interested in CRUS anymore.

People SAY that seiving larger n-ranges is more efficient. I say it's all in the way you look at it. IMHO, sieving a larger range than the n-max being 4 times the n-min (i.e. n=100K-400K) is a waste of CURRENT resources if the total CPU time needed will be over 1-2 years. The higher n-ranges should be sieved by FUTURE resources. After all, who knows, you may not even want to search such a large n-range or all of your k's may already be eliminated. That's why we don't double-check ourselves right after finishing n=260K-400K or something. We do n=100K-260K now and will do n=260K-400K when computers are faster and cheaper in the future

People are assuming a static view of the future in their mathematical models for long-term sieving optimization. IMHO, that's a bad path to take.

That's just my two cents...


Gary