Counting the prime numbers

Jon Maiga, 2021-08-19

In my last article I wrote about an estimation of the prime counting function, π(n)\pi(n). This inspired me to try creating an exact function. Below I present a couple of impractical formulas I found experimentally. There is so much research in the area so I doubt anything below is original.

A recursive formula for the nth primorial

A primorial is like the factorial (4!=1234=244!=1\cdot2\cdot3\cdot4=24) but only prime numbers are used in the multiplication, e.g. 2357=2102\cdot3\cdot5\cdot7=210. We will be using at the second definition of primorials A034386, where the value bumps at indices of primes, pn#p_n\#:

1, 1, 2, 6, 6, 30, 30, 210, 210, 210, 210, 2310, 2310, 30030, 30030, 30030, 30030, 510510, 510510, 9699690, 9699690, 9699690,

I wanted to see if sequencedb could find some simple formulas for the nth primorial, pn#p_n\#. For the automatic search the elementary +,-,*,/ together with the greatest common divisor gcd\gcd and a few other “elementary” functions. One of the simpler generated formulas is the following, with p0#=1p_0\#=1

pn#=gcd(n,gcd(n,pn1#)1)pn1#p_n\#=\gcd(n,\gcd(n, p_{n-1}\#)-1)\cdot p_{n-1}\#

Proof. Let’s examine the two cases, nn is composite or nn is prime.

If nn is composite, then the innermost gcd(n,pn1#)\gcd(n, p_{n-1}\#) equals the square free kernel of nn, rad(n)rad(n). We then subtract one and again check the greatest common divisor with nn, gcd(n,rad(n)1)\gcd(n, rad(n)-1) in a second step.

Since gcd(n,n1)=1\gcd(n,n-1)=1 we get gcd(rad(n),rad(n)1)=1\gcd(rad(n), rad(n)-1)=1 which in turn implies that gcd(n,rad(n)1)=1\gcd(n,rad(n)-1)=1 (since nn has the same prime factors as rad(n)rad(n)). This means that if nn is composite we get pn#=1pn1#p_n\#=1\cdot p_{n-1}\#.

When nn is a prime number, the innermost gcd(n,pn1#)\gcd(n, p_{n-1}\#) equals one since nn is not yet in the primorial. We then subtract one and again check the greatest common divisor with nn, gcd(n,11)=gcd(n,0)=n\gcd(n, 1-1)=\gcd(n,0)=n. This means that if nn is prime we get pn#=npn1#p_n\#=n\cdot p_{n-1}\#.

It turns out that this double gcd structure can be used to create an indicator function for primes. Pretty neat!

primorial[n_]:=primorial[n]=GCD[n, GCD[n, primorial[n-1]]-1]*primorial[n-1]

Formulas for the prime counting function

From our recursive formula, pn#p_n\# we can describe the prime counting function, π(n)\pi(n), the number of prime numbers less or equal to nn A000720

 0, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 14, 14, 14, 14, 15,

π(n)=k=2n(gcd(k,gcd(k,pk1#)1)1)/(k1)\pi(n)=\sum_{k=2}^{n}(\gcd(k,\gcd(k, p_{k-1}\#)-1)-1)/(k-1)

You recognize the double gcd\gcd structure from our primorial definition, the extra subtraction and division just transforms it into the characteristic function of primes (1 if nn is prime else 00). The final summation just adds ones and zeros up.

Note that as an optimization it’s enough to check the greatest common divisors of kk against the square root of kk-th primorial (replace pk1#p_{k-1}\# by pk#p_{\lfloor{\sqrt{k}\rfloor}}\#).

recursive pi

primorial[n_]:=primorial[n]=GCD[n, GCD[n, primorial[n-1]]-1]*primorial[n-1]

With the factorial

Another version can be obtained by replacing the primorial by the factorial, again by utilizing the double gcd structure

π(n)=k=2n(gcd(k,gcd(k,(k1)!)1)1)/(k1)\pi(n)=\sum_{k=2}^{n}(\gcd(k,\gcd(k, (k-1)!)-1)-1)/(k-1)

pi[n_] := Sum[(GCD[k, GCD[k, (k - 1)!] - 1] - 1)/(k - 1), {k, 2, n}]

In fact if we use the factorial we do not need the double gcd\gcd and can get away with something like (note that we need to start counting at n=5n=5)

π(n)=2+k=5n(kgcd(k,(k1)!))/(k1)\pi(n)=2+\sum_{k=5}^{n}(k-\gcd(k, (k-1)!))/(k-1)

pi[1] = 0; pi[2] = 1; pi[3] = 2;
pi[n_] := 2 + Sum[(k - GCD[k, (k - 1)!])/(k - 1), {k, 5, n}]

Almost exact with using a step function

Instead of using our double gcd\gcd structure to create the indicator function for primes here we use a Heavyside step function

π(n)12(n1k=2ntanh(sgcd(k,(k1)!)3s2))\pi(n)\approx\frac{1}{2}\left(n-1-\sum_{k=2}^{n}\tanh\left(s\cdot\gcd(k, (k-1)!) - \frac{3s}{2}\right)\right)

Where ss is any value greater or equal to 11 and is used to sharpen then Heavyside function.



Almost exact with product of cosines

First note that (n1)!n\frac{(n-1)!}{n} is an non-integer iff nn is prime, from this it’s we create the following function cos(kπ(n1)!n)\cos(\frac{k\pi(n-1)!}{n}), where kk runs from 11 to n1n-1.

If nn non prime each cosine will be 11.

If nn is prime wil will get n1n-1 cosines in the between 1-1 and 11 exclusive. A bit informally, the products of those tends towards 0 as nn goes on to larger and larger primes.

π(n)nnk=1n1cos(kπ(n1)!n)\pi(n)\approx n-\sum^{n}\prod_{k=1}^{n-1}\cos\left(\frac{k\pi(n-1)!}{n}\right)

We just sum the products up, invert the result (the leading nn-) and there we have it, an accurate but inefficient prime counting function!

cos product

The slight offset can probably easily be fixed by e.g. exponentiating the product. But let’s keep it simple.



None of the formulas above are practical but it was fun to tinker a bit. I wonder if any of those can be turned into something more analytical than discrete sums and products…