A multiple k/c sieve for Sierpinski/Riesel problems

[geoff]

This version fixes two bugs in the Sobistrator compatibility mode (when using the -j switch):

1. Ranges in SoBStatus.dat are now written with the pmax= line before the pmin= line. Ranges read from SoBStatus.dat and nextrange.txt can now have the lines in either order.

2. Now when the -r switch is given with the -j switch, RieselStatus.dat is used instead of SoBStatus.dat.

[geoff]

When a factor p is found to divide a term k*b^n+c, these versions now check whether p == k*b^n+c, and if so the term is logged as a prime but not removed from the sieve and not reported as a factor.

This behaviour is compatible with srsieve, but not with NewPGen or most other sieve programs. It only ever affects terms with exponents n <= 64.

In some situations leaving a small prime term in the sieve can impede performance, as it can form exceptions to otherwise regular patterns in the remaining exponents. If in doubt, test all small terms with LLR then remove them from the sieve manually.

[Flatlander]

sr1sieve1.exe 1.2.1

The seconds per factor readout seems to be inaccurate. After saying '9 seconds' every time I looked for two hours, I restarted. It now says '63 seconds' which looks about right.

[jasong]

Uh, geoff, I have a request. Someone told me it was a "small" request, but I don't know enough number theory to know whether or not they're correct.

I have a friend, I won't give his name since he wants the information about what he's working on kept secret, but he believes that he's found, through number theory, a k that will produce many, many primes, on both the +1 and -1 sides. The problem is I don't know of an efficient way to sieve twin prime files on fixed n instead of k. That's where my request comes in.

Would it be possible for you to make a twin prime feature in srsieve or sr2sieve(or both) that would allow a fixed k, range of n sieve for twin primes?

[geoff]

Originally Posted by Flatlander

sr1sieve1.exe 1.2.1

The seconds per factor readout seems to be inaccurate. After saying '9 seconds' every time I looked for two hours, I restarted. It now says '63 seconds' which looks about right.

The sec/factor statistic reported by sr[125]sieve is an overall average, it will seem too low if the factor density has dropped significantly since sieving started. (srsieve reports a rolling average based on the last 32 factors, but this also gives unexpected results in some situations).

I haven't been able to think of a good way solve this yet. Any suggestions for a better formula in terms of these variables would be welcome:

t_start:        Time at start of sieve.
t_curr/t_prev:  Time at current/previous status report.
p_start:        Start of sieve range.
p_curr/p_prev:  p at current/previous status report.
f_curr:         Number of factors found so far.

The current formula used by sr1sieve is simply

  (t_curr - t_prev) * (p_curr - p_start)
  --------------------------------------
        (p_curr - p_prev) * f_curr

For anyone trying to decide when to stop sieving and start LLR testing, I would recommend using the method given by axn1 in this post instead of relying on the sec/factor statistic.

[axn]

I forget the actual name of the technique, but you can use a "weighted historical decay" (I totally made that name up -- like I said, forgot what it is called).

Basic idea: you have a historical average , and a new data point , then you calculate the new average as , where is a weighting factor in the range . Higher the , the more dominant the latest data point, and probably more fluctuations in the outcome. The lower the , the smoother the output, but it won't probably react quickly enough to an actual change in the nature of the data. This technique has the obvious advantage that you only need to keep one piece of information at any given time (namely, ) rather than a list of things required for the rolling average, while still obtaining some of the sanity of a rolling average.

For the purpose of the sieve, a in the range 0.05-0.2 should be sufficient. I think it is probably better to plug in f/s rather than s/f in this formula.

Something like

Note that, could well be zero, so ...

And while outputting, do something like:

if rate < 1 
  print 1/rate "sec/factor"
else
  print rate "factor/sec"

[geoff]

These versions fix a bug that could cause a segfault in some situations. Thanks to AES for discovering it.

The bug could occur when the range of n in the sieve is very narrow. Exactly how narrow depends on a lot of factors, but the simplest way to check is to run with the -vv switch and look for a message like:

BSGS range: X1*Y1 - X2*Y2.

If both X1 and X2 (or just X1 for the x86-64 executable) are less than 8 then the bug MIGHT have affected the sieve.

Large projects like SR5, RieselSieve SOB/PSP, etc. were not affected.

[geoff]

Originally Posted by jasong

Would it be possible for you to make a twin prime feature in srsieve or sr2sieve(or both) that would allow a fixed k, range of n sieve for twin primes?

There is a message earlier in this thread on this topic. To sieve for twins of the form k*b^n+/-1, sieve the sequence (k*b^n+1)(k*b^n-1) = (k^2)*(b^2)^n-1.

[geoff]

Originally Posted by geoff

These versions fix a bug that could cause a segfault in some situations. Thanks to AES for discovering it.

After closer checking I see that this bug could only have affected the x86-64 executable, and only srsieve versions 1.2.0-1.2.2 and sr2sieve versions 1.6.3-1.6.13 were affected. The only case where I have been able to actually trigger the bug is when the input sieve file contains exactly one term.

[Cruelty]

Does it mean that the software could have missed some factors or falsely reported factors?

[geoff]

Originally Posted by Cruelty

Does it mean that the software could have missed some factors or falsely reported factors?

It couldn't report false factors, it is possible that factors were missed, however by far the most likely result is that the program would crash soon after starting, and if it didn't crash then it is unlikely that the bug had any other effect.