View Single Post
Old 2021-01-07, 01:39   #123
SethTro's Avatar
Apr 2019

269 Posts

Originally Posted by henryzz View Post
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
SethTro is offline   Reply With Quote