A quick visual reminder of the pattern I’ve just described in the previous couple of posts, looking at the distribution of “possible primes, or “candidate primes” and non-primes after sieving by the n-th prime, for the first three primes.
PP(n) is the set of “possible primes” after sieving to the n-th prime, and A(n) and B(n) are two sets used to get from PP(n-1) to PP(n), by first repeating PP(n-1) Pn times to yield A(n), then multiplying all “possible primes” within PP(n-1) by Pn to get B(n). PP(n) is obtained by removing all members of B(n) from A(n).
The following boxes show positions of “possible primes” within primorials as “1” and non-primes as “_”:
So to get a progressively tighter determination of “possible primes” and non-primes up to the n-th primorial, all we need to is sequentially repeat the lower primorial pattern, PP(i), P(i+1) times (yielding A(i)) and then stretch it by a factor of P(i+1) (yielding B(i)), then intersect the two sets (yielding PP(i)).
What has gone unsaid thus far, but should be self-evident, is that after sieving to the n-th prime, the set of “possible primes” and non-primes between Pn and Pn^2 are actual primes and non-primes. Hence by doing this sequential repetition, stretching and intersection n times, we obtain the complete set of primes to Pn^2. The final box above shows the pattern of possible primes and non-primes within 5# between 5 and 5^2, which includes only the actual primes 7, 11, 13, 17, 19 and 23.
Exactly the same thing happens for higher primes and associated primorials.
I believe this is a much more efficient implementation of the sieve of Eratosthenes.
Note that as n and Pn grow, the gap between Pn^2 and Pn# grows very quickly. In the image above, the upper end of the range containing confirmed primes (5 to 25) is close to the top of the primorial (30). For P7 = 17, P7^2 = 289 and P7# = 510510. The gap between these values grows exponentially.
I’d like to spend a little time working out how much computational effort is required for sieving to some value x, just for kicks. I imagine the computational effort grows exponentially.
For ease of visualization, here is the same sequence of sieving illustrated, but with the patterns for 2# and 3# extended out over 5# (30):