Analytic Computation of the prime-counting Function


Analytic calculation of pi(x) means using information on the Riemann zeta function in order to determine the number of prime numbers not larger than x. The underlying theory for this goes back to B. Riemann who stated an explicit formula involving a sum over the non-trivial zeros of the Riemann zeta function. This formula, after correcting the constant term, was later proven to be true by H. von Mangoldt.

At this time probaly no one would have thought of using this formula for calculating pi(x), since calculating zeros of the Riemann zeta function by hand is much harder than finding prime numbers (it is known that Riemann calculated the first 3 zeros himself, though he did not publish them). It was more than a hundred years later, that H. Riesel and G. Göhl investigated the use of Riemann's explicit formula for calculating the prime counting function. But it turned out, that the sum over zeros converges to slowly in order to calculate pi(x) efficiently.

Later, Lagarias and Odlyzko showed, that calculating the prime counting function analytically could be carried out efficiently after all. Their approach was not based on the explicit formula but they rather used Perron's formula, which expresses pi(x) as a curve integral over a vertical line in the complex plane. Here, the problem of slow convergence arises similarly, but this can be solved by modifying the kernel-function at the expense of having to evaluate a sum over the prime powers in a neighbourhood of x. This resulted in an O(x^(1/2+ε))-algorithm (both for memory an time) to calculate pi(x), which is asymptotically the fastest method we have today. However, they never implemented this method, since the implied constant is expected to be very large.

The Lagarias-Odlyzko method was further analyzed by Galway, who introduced a different kernel-function in order to speed up the convergence of the integral. He also improved the space requirement for calculating the prime numbers in a neighbourhood of x by use of the Atkin-Bernstein sieve. However, he also did not implement this method for calculating pi(x) for large values of x.

Recently, there have been two approaches to calculate pi(x) analytically at large height. One by J. Franke, T. Kleinjung, A. Jost and the author (FKBJ) and one by D. Platt. Both methods are similar in that they rather use part of the zeros of the Riemann zeta function than numerical evaluation of curve integrals. But Franke's method is based on the Weil-Barner explicit formula, while Platt uses a modification of Galway's method. We (FKBJ) were the first to calculate pi(10^24), assuming the Riemann hypothesis for our calculation. This result was later confirmed by D. Platt without any such assumptions. Meanwhile, we have also computed the value pi(10^25) unconditionally, using a new variant of Franke's method developed by the author.

While the methods used by D. Platt and us are similar, the implementations follow different concepts. Platt's implementation has a strong emphasis on rigor, using interval-arithmetic based on multiple precision libraries, which eliminates the need of an error analysis. Our implementation focuses rather on speed, using a 128 Bit fixed-point data type developed by J. Franke. This is why we reach different conclusions for the question whether the cross-over for the analytical method and the combinatorial method has yet occurred.

Values at large height

The values at powers of 2 were calculated under the assumption of the Riemann hypothesis and have not been verified unconditionally, yet.

x pi(x) li(x)
2^77 2,886,507,381,056,867,953,916 2,886,507,381,064,373,208,173.548...
2^78 5,697,549,648,954,257,752,872 5,697,549,648,966,433,789,529.331...
2^79 11,248,065,615,133,675,809,379 11,248,065,615,147,771,807,590.616...
10^24 18,435,599,767,349,200,867,866 18,435,599,767,366,347,775,144.150...
2^80 22,209,558,889,635,384,205,844 22,209,558,889,651,044,698,168.424...
10^25 176,846,309,399,143,769,411,680 176,846,309,399,198,930,392,619.378...

Tables with values of pi(x)

The following tables have been computed analytically. They are ment as an extension of Tomás Oliveira e Silva's tables, calculated with the combinatorial Meissel-Lehmer method. Further extensions of these are planned for the future.