Conjectures with one k remaining

[rogue]

I have some questions and I'm certain that Gary or one of the other lurkers here can answer.

First, given a weight of one of these single k conjectures and a range of n, is there a formula that could tell one how deep that range needs to be sieved? I'm not looking for an exact formula, but I suspect that generating an estimate shouldn't be too hard.

Second, given a weight of one of these single k conjectures and and a range of n, how does one estimate how many n will be left after sieving?

By combining the two answers I can then estimate (given my hardware) how long it would take for me to sieve and PRP test a range of arbitrary size (presuming that no prime would be found).

[Mini-Geek]

Some more exact answers would be great, but here's what I've got:

Originally Posted by rogue

Second, given a weight of one of these single k conjectures and and a range of n, how does one estimate how many n will be left after sieving?

I can't tell you how it is calculated, but if you run sr2sieve, it will tell you how many factors to expect in the range you tell it to search. Subtract some portion (I'm sure an exact formula exists and is not too complicated - don't have time ATM to figure it out) to account for multiple factors on one candidate, and then subtract that from the total, and you've got your estimate candidates remaining. This requires some amount of presieving, not just knowing the weight.

[rogue]

Originally Posted by Mini-Geek

Some more exact answers would be great, but here's what I've got:


I can't tell you how it is calculated, but if you run sr2sieve, it will tell you how many factors to expect in the range you tell it to search. Subtract some portion (I'm sure an exact formula exists and is not too complicated - don't have time ATM to figure it out) to account for multiple factors on one candidate, and then subtract that from the total, and you've got your estimate candidates remaining. This requires some amount of presieving, not just knowing the weight.

That would work, but I still need to know how deeply to sieve.

[gd_barnes]

Those are very tough questions and there is no exact answer. Personally I am very adamant about not sieving a range that would take more than 1-2 years to fully test because sieving and testing software speeds continue to increase so quickly. For that reason, at these levels for a "personal project", I would generally sieve a 2X or 2.5X range. That is where the high n-value is 2 to 2.5 times the low n-value. When doing that, you can test a candidate at ~60% of the n-range and then sieve until the factor removal rate is approximately the length of the test.

If you would like to sieve a range that gives about a 50% chance of prime, that can't very accurately be calculated by weight alone. I'd suggest sieving using srsieve, perhaps, a range of n=100K-500K to P=100M or 1G. Then plug everything into the "odds of prime" spreadsheet, which includes the # of candidates remaining. If the chances of prime are < 50%, then sieve a larger range. If > 50%, then sieve a smaller range. As for how deep to sieve it, that depends on n-max/n-min. If > 2.5X, then pieces need to be broken off and tested with sieving continuing on the remainder. If <= 2.5X, then refer to the first para.


Gary

[rogue]

Originally Posted by gd_barnes

Those are very tough questions and there is no exact answer. Personally I am very adamant about not sieving a range that would take more than 1-2 years to fully test because sieving and testing software speeds continue to increase so quickly. For that reason, at these levels for a "personal project", I would generally sieve a 2X or 2.5X range. That is where the high n-value is 2 to 2.5 times the low n-value. When doing that, you can test a candidate at ~60% of the n-range and then sieve until the factor removal rate is approximately the length of the test.

If you would like to sieve a range that gives about a 50% chance of prime, that can't very accurately be calculated by weight alone. I'd suggest sieving using srsieve, perhaps, a range of n=100K-500K to P=100M or 1G. Then plug everything into the "odds of prime" spreadsheet, which includes the # of candidates remaining. If the chances of prime are < 50%, then sieve a larger range. If > 50%, then sieve a smaller range. As for how deep to sieve it, that depends on n-max/n-min. If > 2.5X, then pieces need to be broken off and tested with sieving continuing on the remainder. If <= 2.5X, then refer to the first para.

Thanks. That gives me an idea.

[rogue]

I have one more question, which I presume has an easy answer. I know that doubling the sieve depth reduces the number of candidates by about 30%. My related question is how does doubling the sieve depth impact removal rate? It is clearly not reduced by 30%. I would guess that it would be around 70%, i.e. if the removal rate is around 1 per second at 1e9, then it would be around 1.7 per second at 2e9. Does that sound right?

[gd_barnes]

Originally Posted by rogue

I have one more question, which I presume has an easy answer. I know that doubling the sieve depth reduces the number of candidates by about 30%. My related question is how does doubling the sieve depth impact removal rate? It is clearly not reduced by 30%. I would guess that it would be around 70%, i.e. if the removal rate is around 1 per second at 1e9, then it would be around 1.7 per second at 2e9. Does that sound right?

On your first statement about reducing the number of candidates, I know that is way too high based on lots of sieving experience but I can't give an exact answer. I believe it depends almost exclusively on the weight of the k-values being sieved and most of the k's sieved here are very low weight. For example, I'm finishing sieving R36 78 k's right now for n=50K-100K. There are ~104K candidates remaining after sieving to P=1T and the optimum sieve depth is P=2.6T. The estimated number of factors quoted by sr2sieve for P=1T to 2.6T is about 3900, which will leave just over 100K candidates remaining at P=2.6T. So in this case...multiplying the sieve depth by a factor of 2.6 only results in a reduction of ~3.8% in the number of candidates remaining. Sieving R6 the remaining 2 k's for n=1M-2M to P=170T was an even more extreme example because one of the k's is extremely low weight. I think a doubling of the sieve depth there only resulted in a 1 to 1.5% reduction.

On the second statement, you have it reversed but I think I know what you mean. You're saying that if at a sieve depth of 1e9, the removal rate is 1 every 1 second, then at 2e9, the removal rate would be 1 every 1.7 secs (vs. 1.7 per 1 sec). Anyway, no, it's almost a straight ratio. When you double the sieve depth, you halve the removal rate. When you triple the depth, you divide the removal rate by 3. Why? Because each candidate has half (or 1/3rd) as much chance of having a specific prime factor that is being tested. So at 2e9, it would be 1 every 2 secs. Note that it would be an EXACT ratio of 2 to 1 or 3 to 1 if you left all candidates in the file to be sieved even after a factor was found for them. But since the programs do not continue to find factors for candidates that already have a factor (If not stopped mid-stream, sr2sieve knows to remove them in memory and not search them anymore.), then such ratios are more like 2.1 or 2.2 to 1 or 3.1 or 3.2 to 1.

I have one more thing to add to a statement that I previously made:

As for how deep to sieve it, that depends on n-max/n-min. If > 2.5X, then pieces need to be broken off and tested with sieving continuing on the remainder.

In determining sieve depth, it depends on more than just the n-max/n-min. It is dependent on removal rate and test length. The question is where to break it off. If sieving n=100K-500K, I would break testing off in n=100K-250K and 250K-500K pieces. So what I would do is pick a candidate at ~60% of the n=100K-250K range and see how long it takes to test. I would then sieve the entire n=100K-500K range until the removal rate equals the test length. After finishing testing n=100K-250K with no prime, I would then pick a candidate at ~60% of the n=250K-500K range and see how long it takes to test followed by sieving the n=250K-500K range until the removal rate equals that length. That's similar to how I did R36. I sieved n=25K-100K and broke off and separately tested/sieved similar pieces for n=25K-50K followed by n=50K-100K. As it turns out the optimum sieve depth for 97 k's for breaking off n=25K-50K from the entire n=25K-100K range was P=1T and for 78 k's for n=50K-100K was P=2.6T. (Note that I removed the 19 k's found prime for n=25K-50K before continuing sieving n=50K-100K.)

Gary

[Puzzle-Peter]

Originally Posted by gd_barnes

If sieving n=100K-500K, I would break testing off in n=100K-250K and 250K-500K pieces. So what I would do is pick a candidate at ~60% of the n=100K-250K range and see how long it takes to test. I would then sieve the entire n=100K-500K range until the removal rate equals the test length.

In this example, only 3/8 of the found factors are from the first part that you are going to test. So the time per factored candidate is much longer than the time needed to LLR a candidate. I assume you have a good reason to not take this into account?

[gd_barnes]

Originally Posted by Puzzle-Peter

In this example, only 3/8 of the found factors are from the first part that you are going to test. So the time per factored candidate is much longer than the time needed to LLR a candidate. I assume you have a good reason to not take this into account?

Yes, because in addition to removing factors from n=100K-250K, you are also removing factors from n=250K-500K at the same time, which saves much time in the future and is quite efficient since the speed of sr(x)sieve scales approximately with the square root of the n-range. It's (almost) the fastest way to sieve and test the entire n=100K-500K range, regardless of whether a prime is found early or not. The hard part is determining what is the optimum range to sieve in the first place based on the fact that we stop testing when finding a prime. If you sieve too large of a range, there is a great chance of finding a prime before you are done resulting in a lot of wasted sieving. If you sieve too small of a range, you lose a lot of sieving efficiency because of the speed scaling mentioned above. I generally recommend sieving an n-max/n-min ratio of 2X to 4X. You could go higher if the k or k's are extremely low weight but I'd suggest almost never going lower.

[rogue]

Should the weights listed in the first post account for the removal of algebraic factorizations? I know that they don't current do so. For example S182 has a weight of 389, but if one removes n where 8*182^n+1 can be factored algebraically, that is reduced to 120. My point is that this conjecture is much harder to prove since so many n are removed for that reason.

These are the updated numbers:

    8*86^n+1  1017	 571
   32*87^n+1   342	 257
   8*182^n+1   389	 120
  27*220^n+1  1136	   0
  27*252^n+1  2164	1312
   8*263^n+1   363	 211
  27*328^n+1   870	 489
   8*353^n+1   613	   0
   8*426^n+1  1288	 486
   8*428^n+1   655	 258
   8*497^n+1   943	 570
   9*724^n+1  1573	1573
   8*758^n+1   549	 281
   8*785^n+1   588	 178
   8*828^n+1  1136	 607
   8*866^n+1   440	   0
   8*930^n+1  1645	1107
   8*953^n+1  1155	 757
   8*983^n+1   853	 425
    4*72^n-1  1211	 838
  64*177^n-1  1607	1307
  32*221^n-1  1317	 988
   4*275^n-1  1472	1472
   8*321^n-1  1017	 606
   8*328^n-1   915	 522
  16*333^n-1  1737	1389
  32*402^n-1  1126	 842
  64*425^n-1  1607	1607
   9*636^n-1  2840	1758
   4*650^n-1  1122	1122
   8*665^n-1  1582	 610
   9*688^n-1  1252	 641
  32*702^n-1  2339	1780
  64*741^n-1  2429	2429
   8*761^n-1  1527	1142
   4*812^n-1  1052	1052
   8*815^n-1  1988	 984
   8*836^n-1  1446	 768
 221*850^n-1  1414	1414
   8*866^n-1  1595	 803
   8*867^n-1   836	 836
   4*968^n-1   938	 938

Note that 27*220^n+1, 8*353^n+1, and 8*866^n+1 all have a weight of 0. I suspect this means that remaining k for those bases are the Sierpinski numbers for those conjectures. I know that the code to compute the Sierpinski/Riesel number doesn't take into account algebraic factorizations.

Could somebody take the time to verify my synopsis? If it is verified, then we have a problem. It is possible that the Sierpinski/Riesel number for other unproven conjectures is wrong.

If I'm wrong, then I must have a bug in my release of srsieve.

[Batalov]

Originally Posted by rogue

Note that 27*220^n+1, 8*353^n+1, and 8*866^n+1 all have a weight of 0.

After sieving, the remaining n's for these are 1 (mod 3), so they don't benefit from algebraic factorization. Shouldn't be 0.