The phenomenon of 'reach' in sieves with regard to prime numbers

61 Views Asked by At

In performing the sieve of Eratosthenes, after sieving serially with the first $n$ primes, the smallest composite number remaining is $p_{n+1}^2$. For example, after sieving with $3$, there are no composite numbers smaller than $5^2=25$ remaining. It is implicit in this sieve that the prime number itself (despite being divisible by itself) is not removed. However, the alternative rule that in sieving with $p_{n+1}$, begin at $p_{n+1}^2$, is a more economical rule in that it preserves in the list the sieving prime, and it avoids testing multiples of $p_{n+1}$ smaller than $p_{n+1}^2$, which have already been eliminated. I refer here to the phenomenon that sieving with $p_n$ effectively screens all numbers up to $(p_{n+1}^2-1)$ as 'reach.'

I highly doubt that I am the first person to recognize this phenomenon, so my question is: Does this phenomenon already have a name or term in the art?

By way of illustrating that his phenomenon is not limited to the sieve of Eratosthenes, I provide two more examples. The sieve of Sundaram (indirectly) identifies odd prime numbers by sieving out $k|(2k+1)\not \in \mathbb P$, leaving a list of $k|(2k+1) \in \mathbb P$. If $2k+1$ is prime, then $2k+1\ne (2a+1)(2b+1)=4ab+2a+2b+1 \Rightarrow k\ne 2ab+a+b$. Since the RHS is symmetrical in $a,b$, we may assume WLOG $b\ge a$. This merely means tha if we have looked at the case $a=1,b=2$, when we look at cases with $a=2$, we need not look at $b=1$, as that is duplicative of an earlier sieving step. Accordingly, for any value of $a$, we need only sieve beginning at $2a^2+2a=2a(a+1)$. To be specific and clear, for $a=1$, we need only begin sieving at $k=2\cdot 1\cdot 2=4$. This corresponds to $2k+1=9$, which is indeed the first odd composite number. In this case, the 'reach' of $a$ is to $2(a^2+a)$.

In sieving for twin primes of the form $6k\pm 1$, we need to sieve out $k|(6k-1) \lor (6k+1)\not \in \mathbb P$, leaving a list of $k|(6k-1),(6k+1) \in \mathbb P$. Such $k$ are described by $k\ne 6ab \pm a \pm b$; see OEIS002822. As with Sundaram, we may assume WLOG $b\ge a$, meaning that for any $a$, we can begin sieving at $k\ge \min(6a^2\pm a \pm a) \Rightarrow k\ge 6a^2-2a$. For $a=1$, $6a^2-2a=4$ and $k=4$ corresponds to $6k\pm 1=23,25$ which is indeed the first pair of numbers of the form $6k\pm 1$ which is not a twin prime. In this sieve, the 'reach' of $a$ is to $(6a^2-2a)$.

I would also be interested in learning of other sieves in which this phenomenon I call 'reach' is observed.