New Maximal Gaps

[rudy235]

Originally Posted by Bobby Jacobs

1370 is the 73rd maximal prime gap. We really want to know if 1552 is the 81st maximal prime gap.

Yes

[mart_r]

Perhaps it would be expedient to consider a complete trial division sieve on large intervals in order for the search to remain exhaustive.

Not sure what's possible in terms of efficient computation, but I'm envisioning a large bitmap, for example 32 GB in size, which could contain almost 3e12 numbers if a wheel size of 30030 is used and only numbers of the form 6k+1 are being looked at (a gap of >= 1432 should appear every about 5e8 integers, only those would have to be checked again for 6k-1 in-between).

To compete, we expect a throughput of at least, say, 3e10 per second. Trial division needs about 210 million primes (i.e. on top about 200 MB to store the halved differences between primes, one per byte), where I guess memory writing is the bottleneck for small primes, "mod"-ing for large primes may be similarly slow (a simplification, I know, there's certainly more to it). Searching for gaps in the sieved interval is the next possible bottleneck, I don't know how much can be done in parallel.
If one such interval could be dealt with in less than two minutes, we'd be happy.

Is this worth any thought? What are the most critical hurdles we are facing?

[Bobby Jacobs]

Yes. This is a good idea. It does not seem to have any hurdles. You did primes up to 2⁶⁴ quickly, so this should be quick, too.

[mart_r]

Originally Posted by Bobby Jacobs

You did primes up to 2⁶⁴ quickly,

Me? Not so much, my performance as a participant back in 2018 was only mediocre, remember that I didn't find any first occurrences. Unlucky me
Also I don't know how to write code comparable to that of Robert Gerbicz's. It takes way more skill and dexterity than a few lines of Pari or Basic...

[Andrew Usher]

The obvious question is: to what extent can that code be re-used in a search beyond 2^64? Also, because of the smaller interval required (less than 2^55), it doesn't need to be as efficient.

[Bobby Jacobs]

It should not be that much harder. When are we going to start the search?

[Andrew Usher]

I still want to follow up this topic. What would count as an official verification, and who's deciding? I have written a segmented sieve but it's also limited to 2^64; as I said, though, efficiency hardly matters for this small range. It doesn't seem that it should be difficult to come up with something that should work, but again what would be necessary to have the results counted as official?

[Cybertronic]

I have a tiny idea...
Every prime p-1 is divisible by 2 ...maybe so you can push up the limit to 2^65.

Example:
Range 11 to 41 -> k= 5 to 20 ; we have limit = 20
Factor 3 kills: k=7,10,13,16,19
Factor 5 kills: k=7,12,17

So primes are: 2k+1, with k=11,14,15,18,20 -> 23,29,31,37,41 > limit

Largest GAP is (18-15)*2=6 -> 31,37

[Andrew Usher]

Yes, I probably thought of that, once ... but realistically, the bigger issue is again that I'm not going to spend time on a program that will be useful only for this unless I know it will be accepted as an official verification by whoever makes the decisions on this - after all, someone else already did write a program and found the new gaps, why duplicate that otherwise?

I would not go much past the limit required to verify the new gaps anyway; my resources are far short of the distributed effort that originally went to 2^64.

[mart_r]

I am testing a SOE implementation in Excel/VBA, thus far I have the differences of the primes up to 75011^2-2 (which would suffice for a search up to about 3.166e19) packed into an array of 131469743 short integers (16-bit), with two differences per integer.
Currently the division of the 65-bit offset number by the up-to-33-bit numbers is the bottleneck - it took 6 minutes in total to churn through an interval of 600 million! -, so I'm wondering whether it would be faster to store the offsets for the sieve and the increment values for each interval to be sieved in another two array variables, so we get rid of the division step at the cost of a memory read-out. Apart from the few 33-bit numbers we would need, most of the numbers to do TDing with could be long integers (32-bit), and we would need about 2 x 203 million of them (plus a couple more for the 33-bit TD primes), so storing the prime differences, offset and increment values would take about 2 GB of RAM, which is already too heavy for my programming environment.
My 6 min per 6e8 was a first test run where for the sieve I used an array of 300 million 16-bit numbers with only one bit per number used. I wanted to rewrite it to use 32-bit integers and all bits of them for the sieve, yet with the planned setup it can't possibly be much faster than 1e8 per second. I mean, if ever my code should work properly, I would run it, but be prepared that it would take a very long time for me to give updates on the progress...

Again, my idea from before: if sieving is the main bottleneck it might make sense to only search one residue class mod 6 and look for gaps >= 716 (= 1432/2), and check the complementary residue class (possibly in a separate, parallel routine) if such a gap is found. If searching for the gaps in the sieved interval is the bottleneck, then it should be more efficient to sieve as usual, as larger intervals can then be skipped in the sieved array.

[Bobby Jacobs]

I cannot wait for the gaps above 2⁶⁴ to be found. Let's get it started!