Jon Maiga, 2021-08-19
In my last article I wrote about an estimation of the prime counting function, . 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 primorial is like the factorial () but only prime numbers are used in the multiplication, e.g. . We will be using at the second definition of primorials A034386, where the value bumps at indices of primes, :
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, . For the automatic search the elementary +,-,*,/ together with the greatest common divisor and a few other “elementary” functions. One of the simpler generated formulas is the following, with
Proof. Let’s examine the two cases, is composite or is prime.
If is composite, then the innermost equals the square free kernel of , . We then subtract one and again check the greatest common divisor with , in a second step.
Since we get which in turn implies that (since has the same prime factors as ). This means that if is composite we get .
When is a prime number, the innermost equals one since is not yet in the primorial. We then subtract one and again check the greatest common divisor with , . This means that if is prime we get .
It turns out that this double gcd structure can be used to create an indicator function for primes. Pretty neat!
primorial[0]=1;
primorial[n_]:=primorial[n]=GCD[n, GCD[n, primorial[n-1]]-1]*primorial[n-1]
From our recursive formula, we can describe the prime counting function, , the number of prime numbers less or equal to 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,
You recognize the double structure from our primorial definition, the extra subtraction and division just transforms it into the characteristic function of primes (1 if is prime else ). The final summation just adds ones and zeros up.
Note that as an optimization it’s enough to check the greatest common divisors of against the square root of -th primorial (replace by ).
primorial[0]=1;
primorial[n_]:=primorial[n]=GCD[n, GCD[n, primorial[n-1]]-1]*primorial[n-1]
pi[n_]:=Sum[(GCD[k,GCD[k,primorial[k-1]]-1]-1)/(k-1),{k,2,n}]
Another version can be obtained by replacing the primorial by the factorial, again by utilizing the double gcd structure
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 and can get away with something like (note that we need to start counting at )
pi[1] = 0; pi[2] = 1; pi[3] = 2;
pi[n_] := 2 + Sum[(k - GCD[k, (k - 1)!])/(k - 1), {k, 5, n}]
Instead of using our double structure to create the indicator function for primes here we use a Heavyside step function
Where is any value greater or equal to and is used to sharpen then Heavyside function.
pi[n_,s_]:=1/2(n-1-Sum[Tanh[s*GCD[k,(k-1)!]-3s/2],{k,2,n}])
First note that is an non-integer iff is prime, from this it’s we create the following function , where runs from to .
If non prime each cosine will be .
If is prime wil will get cosines in the between and exclusive. A bit informally, the products of those tends towards 0 as goes on to larger and larger primes.
We just sum the products up, invert the result (the leading ) and there we have it, an accurate but inefficient prime counting function!
The slight offset can probably easily be fixed by e.g. exponentiating the product. But let’s keep it simple.
cp[n_]:=Product[Cos[k*(n-1)!*Pi/n],{k,n-1}]
pi[n_]:=n-Sum[cp[k],{k,n}]
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…