# Counting primes by counting numbers of the form $6k \pm 1$ which are not prime

Again, pondering on twin primes, I came upon the following result. It baffles me a bit, so could someone give more intuitive reasoning why it works.

First, define a function $P_6$ as $$P_6(n)=\begin{cases} 0, \ \ 6n-1 \not\in \mathbb P \wedge 6n+1 \not\in \mathbb P \\ 1, \ \ (6n-1 \not\in \mathbb P \wedge 6n+1 \in \mathbb P) \vee (6n-1 \not\in \mathbb P \wedge 6n+1 \in \mathbb P)\\ 2, \ \ 6n-1 \in \mathbb P \wedge 6n+1 \in \mathbb P \end{cases}$$

So $P_6(n)$ has value $0$ if neither of the numbers around $6n$ is a prime, $1$ if either but not both are primes and $2$ is both are.

Let sets $P_6^0,P_6^1,P_6^2$ be the corresponding sets of indexes where $P_6 = 0,1 \vee 2$, so, for example, $\forall n\in P_6^1, P_6(n) = 1$

Define three new functions using the indicator functions of above sets:

\begin{cases}
\pi_{6\bullet}^0 (n) = \sum_{i=1}^n 1_{P_6^0}(i) \\
\pi_{6\bullet}^1 (n) = \sum_{i=1}^n 1_{P_6^1}(i) \\
\pi_{6\bullet}^2 (n) = \sum_{i=1}^n 1_{P_6^2}(i)
\end{cases}

So these functions tell how many such indexes $1 \leq s \leq n$ there are for whom the number of primes surrounding $6s$ is $i$, $i \in \{0,1,2\}$.

These functions have following relations: $$\pi_{6\bullet}^0 (n)+\pi_{6\bullet}^1 (n)+\pi_{6\bullet}^2 (n) = n \ \ \ \ \ (1)$$ and $$\pi(6n+1)-2 = \pi_{6\bullet}^1 (n)+2 \pi_{6\bullet}^2 (n) \ \ \ \ \ (2).$$

Here $\pi(n)$ is the prime counting function and it has argument $6n+1$ because the biggest number we test is indeed $6n+1$ and we have to remove $2$ because the first two primes are not reachable via number six.

Now, from (1) we get $$\pi_{6\bullet}^2 (n) = n-\pi_{6\bullet}^0 (n)-\pi_{6\bullet}^1 (n) \ \ \ \ \ (3).$$

Substituting to (2) we get $$\pi(6n+1) = 2n-2\pi_{6\bullet}^0 (n)-\pi_{6\bullet}^1 (n)+2.$$

This works. For example $\pi_{6\bullet}^0 (5000) = 2223,$ and $\pi_{6\bullet}^1 (5000) = 2311$, and $10000-2*2223-2311+2 =3245 = \pi(30001).$

Can someone offer a bit more intuition on how this works? The $(2\pi_{6\bullet}^0 (n)+\pi_{6\bullet}^1 (n))$ is the number of numbers of the form $6k-1 \vee 6k+1$ between 5 and $6n+1$ which are not prime and when this is subtracted from $2n$ we get number of primes between 5 and $6n+1$. How?

#### Solutions Collecting From Web of "Counting primes by counting numbers of the form $6k \pm 1$ which are not prime"

An integer has a chance of being prime if it is not divisible by 2 or 3. Call such a number a potential primes. The number of potential primes between 5 and $6n+1$ (again, that means integers not divisible by 2 or 3) is $2n-2$, because numbers not divisible by 2 or 3 occur in pairs $(6k-1, 6k+1)$ around the multiples of 6.

To get the actual number of primes, we have to subtract from $2n$ the number of these potential primes that are not prime. For each $k \le n$, see if the two neighbors of $6k$ are primes, and if not, subtract from $2n$ accordingly. If neither $6k-1$ nor $6k+1$ is prime, subtract 2 to account for the two non-primes. If exactly one neighbor of $6k$ is prime, we subtract 1. We can subtract all the 2’s at once by subtracting $2\pi_{6\bullet}^0 (n)$, and we can subtract all the 1’s at once by subtracting $\pi_{6\bullet}^1 (n)$. This gives the number of primes between 5 and $6n+1$. Taking into account the primes 2 and 3, the result is the formula you wanted an explanation for, $$\pi(6n+1) = 2n-2\pi_{6\bullet}^0 (n)-\pi_{6\bullet}^1 (n)+2\textrm{.}$$