mersenneforum.org Prime Gap Theory
 Register FAQ Search Today's Posts Mark Forums Read

 2021-08-02, 20:54 #133 SethTro     "Seth" Apr 2019 22·97 Posts Dana's code always tests low side first, then high side. My code does the same thing (always testing the low side first). Even if one side is significantly more dense. For large numbers (>5000 digits) where PRP take significant amounts of time, these are all theoretical optimizations to find large gaps faster. 1. Calculating $ P(\text{record gap} \mid sieve)$ And skipping intervals where the probability is small (e.g. the both sides are more dense with unknowns than expected). 2. Calculating $ P(\text{record gap} \mid \text{upper sieve, lower gap})$ Skipping finding the 2nd surrounding prime when the first prime is nearby. 3. Calculating $\sum{P(\text{lower gap}) * H(P(\text{record gap} \mid \text{upper sieve, lower gap}) < \text{skip prob})}$ vs $\sum{P(\text{upper gap}) * H(P(\text{record gap} \mid \text{lower sieve, upper gap}) < \text{skip prob})}$ This would be more time consuming, roughly O(n^2) vs O(n), but would tell us which side (upper / lower, next / previous) is more likely to result in skipping. A newer calculation shows this gives only a 0-3% speedup and requires a LOT of extra code. Dana's code implements 1, my code implements 1 and 2. I would not recommend optimization 3 in practice. Last fiddled with by robert44444uk on 2021-08-04 at 14:24
2021-08-04, 14:24   #134
robert44444uk

Jun 2003
Oxford, UK

3×661 Posts

Quote:
 Originally Posted by SethTro Dana's code always tests low side first, then high side. My code does the same thing (always testing the low side first). Even if one side is significantly more dense.
Danaj's surround_primes code also allows for a limited range to be checked (delta). As deficient primorials have very few prime candidates within 2 normal gap widths (and sometimes 4 times) from the centre, then there is little cost in carrying out this check. This would then eliminate those candidates where the plus side has a prime within 2 or 4 widths of the centre point.

Last fiddled with by robert44444uk on 2021-08-04 at 14:26

 Similar Threads Thread Thread Starter Forum Replies Last Post Nick Number Theory Discussion Group 6 2016-10-14 19:38 firejuggler Math 0 2016-07-11 23:09 Ricie Miscellaneous Math 24 2009-08-14 15:31 jasong Math 3 2005-05-15 04:01 clowns789 Miscellaneous Math 5 2004-01-08 17:09

All times are UTC. The time now is 12:06.

Mon Dec 6 12:06:17 UTC 2021 up 136 days, 6:35, 0 users, load averages: 1.84, 1.66, 1.55