A multiple k/c sieve for Sierpinski/Riesel problems

[masser]

I think geoff should probably do it; he created the code and probably should administer the Prime Pages code for it...

What do you say, geoff?

[geoff]

Originally Posted by masser

I think geoff should probably do it; he created the code and probably should administer the Prime Pages code for it...

What do you say, geoff?

I have created a Prime Pages entry for srsieve http://primes.utm.edu/bios/page.php?id=905.

Version 0.3.0 splits base b sequences into base b^Q subsequences, but I haven't worked out how to choose the optimal Q yet, and unfortunately the wrong choice can result in a large slowdown.

Experiment with the --limit-base command line switch to get the best throughput for a particular sieve:

--limit-base=X will choose the largest possible Q from the divisors of X.
--limit-base=0 (default) will choose the largest possible Q.
--limit-base=1 will effectively turn off this feature.

There have been a lot of changes to the code recently, so there may be new bugs. Version 0.1.24 is probably the most stable, so use that or NewPGen as a double check if in doubt.

[konrad127123]

Could you add a feature where it would try various Q's and time them for a short while at the start and so decide on the optimal one to use?

[geoff]

Originally Posted by konrad127123

Could you add a feature where it would try various Q's and time them for a short while at the start and so decide on the optimal one to use?

Better than that:

Version 0.3.1 corrects a problem that made 0.3.0 slow when working with base b^Q for large values of Q. The --limit-base switch should not be needed as the default behaviour of simply choosing that largest possible Q should now be optimal in most cases.

[konrad127123]

Have you tried using values of Q larger than 48? This could possibly increase the sieve speed further.

[geoff]

Just some changes for the Base 5 project sieve:

sr5sieve now writes factors to factorsNNNN.txt where NNNN is the beginning of the sieve range as a multiple of 10^9, as given in the sr5work.txt file. This should make it easier to submit completed ranges when there are other ranges queued up, as each range gets written to a different file.

'sr5sieve -g K N0 N1' will generate a NewPGen file for the terms N0 <= n < N1 of the sequence K*5^n+/-1 in sr5data.txt, for input to PRP/LLR.

Originally Posted by konrad127123

Have you tried using values of Q larger than 48? This could possibly increase the sieve speed further.

(See this thread)

[geoff]

This version fixes a bug present in versions 0.3.0 to 0.3.6 that could cause candidates to be lost from the sieve when the sieve range started at n=0 and the term k*b^0+c was prime. (So the bug didn't affect the Base 5 distributed sieve).

[geoff]

sr5sieve, the base 5 project sieve, is now in a seperate package available here.

srsieve now recognises sequences in which each term is of the form A^(2^y)+B^(2^y) and only sieves them for factors of the form X*2^(y+1)+1.

[geoff]

This version fixes a bug reported by Citrix that caused wrong results for k > 2^31-1.

Also added is the --mod=X,a,b,... command line switch that causes the sieve to only try factors p of the form p = a (mod X), p = b (mod X), etc.

[geoff]

For sequences k*b^n+c, k and c can now be 64-bit values: 0 < k < 2^64, 0 < |c| < 2^63.

When sieving in base b^Q, Q is now chosen using a different algorithm and should result in a small speedup in many cases, although it is possible some sequences will be slower. Use the --verbose switch to print which base is being used, and the --force-base=X switch to force base b^X to be used if necessary.

(It looks like base 5^60 might now be slightly faster than base 5^48 for the Base 5 Project distributed sieve, so I'll modify sr5sieve once this has had a bit more testing).

[axn]

Originally Posted by geoff

(It looks like base 5^60 might now be slightly faster than base 5^48 for the Base 5 Project distributed sieve, so I'll modify sr5sieve once this has had a bit more testing).

After removing 3 k's for the latest primes, this is what's coming up now:
Split 309 base 5 sequences into 7998 base 5^240 subsequences.:surprised