lBefore I can get my hands on more numbers from the scan, let's go back to 147. C-ving.

For the prime 1511 and higher, there is not enough data to get a complete histogram and there are histograms with 3 holes. We already know that the holes are symmetric : mod = n1 + n2 + 1; From there, it should be easy to select which hole is meaningless.

Let's consider 3 holes H1, H2 and H3. Any of them could be a false hole, from an incomplete dataset. It would be easy to construct candidate moduli to test (using modulo arithmetic and sieving with other known good sieves) but this would be heavy.

Instead, using the symmetries, we can compute H1+H2, H1+H3, and if neither sum matches then H1 is the bad one.

OK so we might get a few more entries in the sieve.

But I think there is an even simpler way to solve this.

.

.

.

An even more insteresting behaviour I have noticed is that ...

The N1 and N2 are unique !

Look at the numbers in the list at 147. C-ving. It starts with

11 3  7
19 4  14
29 5  23
31 12  18
41 6  34
59 25  33
61 17  43
71 8  62
79 29  49
89 9  79
101 22  78
109 10  98
131 11  119

1 is pointless and 2 is already taken by base=5.

In the 13 first bases of the list above, we can already find the numbers from 3 to 12, 13 is given by base 181 a bit below, and 14 is coming back at the top of the sieve at base 19.

So when a hole-y histogram has more than 3 holes, not only can we eliminate those that have no complement, but we can also eliminate all the numbers that have appeared before !

.

.

.

To solve the first problem, for any number of holes (not just 3) without adding crazy combinatorial code, it's easy : work with only 1/2 of the histogram. The upper half is "folded" if it is above one half of the base.

Then, there might still be holes. The previous entries of the sieve can be scanned, to check which numbers have appeared before, and strike the corresponding holes.

With these enhancements, I bet the algorithm can create increasingly better and better sieves, building from the previous ones.

It looks more and more like a reverse sieve now :-)
.

.

.

Result : with the new algorithm, we can now sieve up to base 4159!

Now 262 prime bases are checkd! That's almost the double of the 143 known before. And the format has changed since N1 and N2 are folded into N1 only, for a smaller footprint. The generator is also way more efficient, using less computations for the small bases for example.

Glee !

The sieving power decreases though, the original moduli up to 131540 give 31614 candidates vs 34495 with almost half the prime bases. That's 4.16 vs 3.81, not a big ratio. The number of bases has doubled but the sieving only dropped by about 10%. A lot of non-sieved numbers puzzle me though. Why are they not caught and how can they get cleaned up ?

Get your own copy of the files at sieve_booster.tgz !

Oh and w32 still seems "good" so far:

[yg@localhost gPEAC_scan]$ for i in $(seq 1 63)
  do echo -n "$i  "
  ./sieve_out $((2**i))
  echo
done |grep OK
4  16 OK 
6  64 OK  known bad
10  1024 OK 
15  32768 OK known bad
16  65536 OK 
23  8388608 OK known bad
24  16777216 OK  known bad
26  67108864 OK
30  1073741824 OK ?
31  2147483648 OK (probing)
32  4294967296 OK (only 13.603.546.275 for the primary orbit)
34  17179869184 OK (only  118.781.994.407 iterations)
35  34359738368 OK (only 15.959.149.451 iterations)
40  1099511627776 OK (just 8803509994715 iterations)
51  2251799813685248 OK ?
52  4503599627370496 OK ?
54  18014398509481984 OK ?
55  36028797018963968 OK ?
59  576460752303423488 OK ?
60  1152921504606846976 OK ?
63  9223372036854775808 OK ?

 I can't test w64 because this exceeds the 64-bit internal representation of bash and my program, but it's just a matter of using bingint.

Update: see log 154. w32 "Just in case" for updated values