1

Total noob question so please bear with me.

There seems to be several formulae which estimate the number of primes below $n$, but none which give the exact number (short of computing the primes directly).

Is that because it has been proven that such a formula does not exist? Or because it hasn't been discovered yet?

ie. A formula akin to area = πr² that gives an instant answer rather than using ∑

Thanks!

Fidel
  • 191

1 Answers1

5

In other words - Is there an explicit analytical formula for the prime-counting function $\pi(n)$?

Yes there are many. If it's about computation time one would use boundaries, resulting from the prime number theorem.

If it's about easyness one may use Wilsons theorem to get to an anaytical expression or other theorems, for example $$\pi(n) = \sum_{j=1}^{n}\left\lfloor\cos^2\pi\frac{(n-1)!+1}{n}\right\rfloor,$$ where $\lfloor\cdot\rfloor$ is the floor function. Basically the whole function inside the sum is an indicator function, that returns $1$ if $n$ is prime and $0$ otherwise.

If it's about beauty, than it's this formula:

$$\pi(x)=R(x)-\sum_{\rho}R(x^\rho),$$ where $$R(x) := \sum_{n=1}^{\infty}\frac{\mu(n)}{n}\operatorname{li}(x^{1/n}),$$ $\mu$ the Möbius-function, $\operatorname{li}$ the logarithmic integral and $\rho$ are all the zeros of the $\zeta$-function.

vitamin d
  • 5,783
  • Fascinating, thank you vitamin. I assume any of these 'sum of' type formulae require long computations. Can there be a formula like 'area = πr²' which gives an instant answer? – Fidel Feb 20 '21 at 23:33
  • I have never seen the cosine formula before. Do you have a reference for this? – Randall Feb 21 '21 at 00:02
  • @Randall Yes I do. The paper is written in german but I don't think that's a problem. The formulas inclusive derivation and prove are one the pages 4-6. https://riemannhypothesis.info/schepke_primzahlerzeugende_folgen.pdf – vitamin d Feb 21 '21 at 00:06
  • Wow. Thank you. – Randall Feb 21 '21 at 00:08