Prime Gap Theory

[henryzz]

What is the logic behind searching one side before the other? Wouldn't it be better to test the denser central region first(assuming a primorial divisor) as it will probably be needed for a record?

[SethTro]

Originally Posted by henryzz

What is the logic behind searching one side before the other? Wouldn't it be better to test the denser central region first(assuming a primorial divisor) as it will probably be needed for a record?

Not sure I quite understand the question. Is it
1) Why do I always search downwards before upwards?
2) Why do I give up after one search?

1) I don't think it matters which direction you search or if you search the denser / less dense side first.

It's possible there's some better out of order search scheme that alternates testing values on each side and from different points in the sieve but let's ignore that and focus on searching one side till we find the closest prime in that direction; Note this always takes the same expected number of PRP tests minus the small < 0.5% chance that we exceed the sieve length.

My mental justification was: If one side is twice as dense and we search that side first; the expected value is nearer but the sparseness on the other side makes it still likely to find a record. If we search the sparse side first then we get a larger value but the other side is denser so it's similar.

Let me know if this doesn't pass a smell test and we can try to validate by running a post-facto analysis over some run with --no-side-skip.

for 2) I wrote a bit about this at https://github.com/sethtroisi/prime-...ne-sided-tests

[henryzz]

Originally Posted by SethTro

Not sure I quite understand the question. Is it
1) Why do I always search downwards before upwards?
2) Why do I give up after one search?

1) I don't think it matters which direction you search or if you search the denser / less dense side first.

It's possible there's some better out of order search scheme that alternates testing values on each side and from different points in the sieve but let's ignore that and focus on searching one side till we find the closest prime in that direction; Note this always takes the same expected number of PRP tests minus the small < 0.5% chance that we exceed the sieve length.

My mental justification was: If one side is twice as dense and we search that side first; the expected value is nearer but the sparseness on the other side makes it still likely to find a record. If we search the sparse side first then we get a larger value but the other side is denser so it's similar.

Let me know if this doesn't pass a smell test and we can try to validate by running a post-facto analysis over some run with --no-side-skip.

for 2) I wrote a bit about this at https://github.com/sethtroisi/prime-...ne-sided-tests

To some extent I think it makes sense to try and find one of the end points as that allows for an early skip(as that is done 90% of the time now). I wonder whether skips could be done faster/more frequently/more accurately if a small portion of the other side is also tested early(before aiming for finding an end point). Record gaps very rarely have 90%(optimal figure to be determined based on the records list) on one side so 10% should be tested early on both sides.

[SethTro]

Originally Posted by henryzz

To some extent I think it makes sense to try and find one of the end points as that allows for an early skip(as that is done 90% of the time now). I wonder whether skips could be done faster/more frequently/more accurately if a small portion of the other side is also tested early(before aiming for finding an end point). Record gaps very rarely have 90%(optimal figure to be determined based on the records list) on one side so 10% should be tested early on both sides.

I've been pondering this for a while and you've changed my mind I should be testing the least dense portion of the interval.

I plotted some examples and it appears that if d the divisor has few divisors (1, 2, 3) the center is clearly less dense but as d has more divisors (6,30,210) it's not clear how much this helps.

I'm not sure how to measure the improvement but I'd guess this would give another 5-15% improvement but would take some reasonable amount of code. I've recorded it in the low priority TODOs but I'm unlikely to write this soon (happy to help anyone interested in coding it up).

[Bobby Jacobs]

When d=6, the coprimes are 1 and 5, so the center is not very dense. When d=30, the coprimes are 1, 7, 11, 13, 17, 19, 23, 29, so the center is dense. When d=210, the coprimes are 1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209, so the center is very dense.

[SethTro]

Originally Posted by Bobby Jacobs

When d=6, the coprimes are 1 and 5, so the center is not very dense. When d=30, the coprimes are 1, 7, 11, 13, 17, 19, 23, 29, so the center is dense. When d=210, the coprimes are 1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209, so the center is very dense.

coprimes hides a lie with d=210 for any given m half of the coprimes will be divisible by 2, 1/3 by 3 and 1/5 by 5 so the center is still not very dense.

[MJansen]

Hi Seth and Bobby,

when you plot the remaining candidates of a primorial value divided by 6, 30, 210, 2310 etc. you will find the remaining candidates with divider 6 are few close to the primorial center value but many a little distance from the center. The larger the divider, the more spread out the candidates are.

So in a nutshell: The larger the divider, the fewer there are candidates around the center.
But since the remaining candidates (say with divider 30030), are stronger candidates, chance is you will mostly find smaller gaps with the occasional find of a larger gap.

There has been a post somewhere/somewhen that had a very nice graphic representation of that observation.
You can easily check this yourself by writing a simple script that for instance prints the remaining candidates in an interval p(100)#/D +/- 10*P(100). after deleting all candidates that divide by the factors of the divider D.
So D = 30030 has factors 2, 3, 5, 7, 11, 13 --> remove all candidates that can be divided by one (or more) of these factors
So D = 30 had factors 2, 3, 5 --> remove all candidates that can be divided by one (or more) of these factors

Compare the distribution of the candidates and you will see the pattern emerge, as I described above.

Hope this is clear
Michiel