Prime Gap Theory - Page 13

SethTro · 2021-08-02, 20:54

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.

robert44444uk · 2021-08-04, 14:24

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.

2021-08-02, 20:54	#133
SethTro "Seth" Apr 2019 100101011₂ 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 $<br /> P(\text{record gap} \mid sieve)<br />$ And skipping intervals where the probability is small (e.g. the both sides are more dense with unknowns than expected). 2. Calculating $<br /> P(\text{record gap} \mid \text{upper sieve, lower gap})<br />$ 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})}<br />$ 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Basic Number Theory 4: a first look at prime numbers	Nick	Number Theory Discussion Group	6	2016-10-14 19:38
Before you post your new theory about prime, remember	firejuggler	Math	0	2016-07-11 23:09
Mersene Prime and Number Theory	Ricie	Miscellaneous Math	24	2009-08-14 15:31
online tutoring in prime number theory	jasong	Math	3	2005-05-15 04:01
Prime Theory	clowns789	Miscellaneous Math	5	2004-01-08 17:09