3

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: \begin{equation} \pi_{6\bullet}^0 (n)+\pi_{6\bullet}^1 (n)+\pi_{6\bullet}^2 (n) = n \ \ \ \ \ (1) \end{equation} and \begin{equation} \pi(6n+1)-2 = \pi_{6\bullet}^1 (n)+2 \pi_{6\bullet}^2 (n) \ \ \ \ \ (2). \end{equation}

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 \begin{equation} \pi_{6\bullet}^2 (n) = n-\pi_{6\bullet}^0 (n)-\pi_{6\bullet}^1 (n) \ \ \ \ \ (3). \end{equation}

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?

Valtteri
  • 3,154

3 Answers3

4

An integer has a chance of being prime if it is not divisible by 2 or 3. Call such a number a potential prime. 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{.}$$

Steve Kass
  • 14,881
0

The following method can calculate $\pi(n)$ by finding the composite numbers in the arithmetic progressions (ap) $(6k+1)$ and $(6k-1)$. For any given number n, n/3 of those numbers are multiples of 3 and n/3 are multiples of 2. So we only need to look at n/3 numbers to determine $\pi(n)$. In other words, we only need to count the number of composites in the two arithmetic progressions. To be able to count them, we need to be able to tell which one is prime and which is composite.

The relation between $\pi(x)$ and $c(x)$ (c(x) counts the number of composites below n/3 in the two arithmetic progressions) is $$ \pi(x) + c(x) =n/3$$ Of course, we need to add 2 to $\pi(x)$ at the end to account for the primes 2 and 3.

First we need to index the numbers in the two arithmetic progressions. The indices will tell us which is a composite number and which is not. The indices will be listed below the ap.

$$7,13,19,25,31,37,43,49,55,61,67...$$ $$1,2,3,4,5,6,7,8,9,10,11...$$
$$5,11,17,23,29,35,41,47,53,59,65...$$ $$1,2,3,4,5,6,7,8,9,10,11...$$

It's easier to tell which number is composite. To find the composite numbers, we need to consider the 3 following products.
Products of the form $$K=(6k_{1}+1)(6k_{2}+1)$$ $$L=(6k_{1}-1)(6k_{2}-1)$$ $$M=(6k_{1}+1)(6k_{2}-1)$$

The matrices $K$ and $L$ are symmetric so we do not need to calculate all the elements. The matrix $M$ is not symmetric so we do need to calculate all the elements. When we calculate the matrix elements, we don't calculate the product of two numbers like $7*7=49$. We in fact calculate the index of 49 which is given by: $$K(i,j)=6i*j+(i+j)$$ with (i,j) running through the values 1,2,3,4,5... so $7*7$, the first element of $K$ will be represented by $7*7=6*1*1 + 1+1=8$. The second element $7*13= 6*1*2 +1+2=15$ but it is also $7*13=8 + 7$. That is the second element is equal to the first plus $7$. We can build the whole first column of the matrix $K$ with doing only the first multiplication. The columns of the matrix $K$ are basically arithmetic progressions themselves.

The first two columns of indices will look like this: $$8,15,22,29,36,43,50,...$$ $$28,41,54,67,80,93,106,...$$

Once we have calculated the indices, we can go back to the $(6k+1)$ ap of $7,13,19,25,...$ and match the index 8 with its value on the list on indices $1,2,3,4,5,...$. We will see that 8 is the index of $49=7*7$. So when an index from the matrix $K$ matches an index on the $(6k+1)$ ap, we know the corresponding number ($49 in this case) is a composite since they can be produced by a multiplication.

Since the indices below 8 were not produced in the matrix $K$, we can conclude that the numbers of the ap $(6k+1)$ whose index is below 8 are all primes. It's true for all numbers except 25 with an index of 4. The simple reason for that is because the index of $25=5*5$ is produced in the matrix $L$. It's in fact the first element of the matrix $L$. The reason is because a product of two $(6k-1)$ numbers produces a number of the form $(6k+1)$.

In other words, we cannot declare that a number on the $(6k+1)$ ap is a prime until we cannot match its index with an element of the matrices $K$ or $L$.

The elements of the matrix $L$ are given by $L=6ij - (i+j)$. They are calculated separately but the indices will be used with the arithmetic progression (ap) $(6k+1)$. The indices of the first column of the matrix $L$ is given by: $$4,9,14,19,24,...$$

We build the matrix $M$ the same way. $M(i,j)=6ij + (i-j)$ but we need to remember that $M(i,j)$ is not equal to $M(j,i)$. So we need to calculate all the elements of the $M$ matrix.

For all three matrices, we stop the calculation when we reached the value of $N/6$ since a value greater than $N/6$ will produce a number larger than $N$. If $N=900$, we only need to look at $N/3=300$ numbers (or indices) with an index of at most $900/6=150$.

There are probably ways to make the method more efficient by avoiding the storage of large matrices but I don't know enough about that field.

user25406
  • 1,048
  • 1
  • 9
  • 16
0

I proposed "matrix sieve" algorithm for finding primes:

Positive integers which do not appear in both arrays $A1(i,j)=6i^2+(6i−1)(j−1)$ and $A2(i,j)=6i^2+(6i+1)(j−1)$

                        |  6   11    16     21   ...|
            A1(i,j) =   | 24   35     46    57   ...|
                        | 54   71     88   105   ...|
                        | 96  119    142   165   ...|
                        |...  ...  ...   ...     ...|


                         |  6    13   20    27   ...|
             A2(i,j) =   | 24    37   50    63   ...|
                         | 54    73   92   111   ...|
                         | 96   121  146   171   ...|
                         |...      ...       ...        ...   ...|

are indexes k of primes in the sequence $S1(k)=6k−1$ .

Positive integers which do not appear in both arrays $A3(i,j)=6i^2−2i+(6i−1)(j−1)$ and $A4(i,j)=6i^2+2i+(6i+1)(j−1)$

                               | 4       9     14       19.. |
                               |20      31     42       53...|
                               |48      65     82       99...|
                      A3(i,j)= |88     111     134     157...|
                               |...   ...      ...     ...   |

                        | 8      15      22     29 ..|
                        |28     41       54     67...|
               A4(i,j)= |60     79       98     117..|
                        |104   129      154    179...|
                        |...    ...     ...     ...  |

are indexes k of primes in the sequence $S2(k)=6k+1$. Since all primes (except 2 and 3) are in one of two forms 6k−1 or 6k+1 so we can find primes simply by picking up positive integers which do not appear in these arrays.(C++ code see http://www.planet-source-code.com/vb/scripts/BrowseCategoryOrSearchResults.asp?lngWId=3&blnAuthorSearch=TRUE&lngAuthorId=21687209&strAuthorName=Boris%20Sklyar&txtMaxNumberOfEntriesPerPage=25

Boris Sklyar
  • 107