Computing 𝜋(𝑥) analytically

Platt, David

doi:10.1090/S0025-5718-2014-02884-6

Computing $\pi \left (x\right )$ analytically
HTML articles powered by AMS MathViewer

by David J. Platt PDF

Math. Comp. 84 (2015), 1521-1535 Request permission

Abstract:

We describe a rigorous implementation of the Lagarias and Odlyzko Analytic Method to evaluate the prime counting function and its use to compute unconditionally the number of primes less than $10^{24}$.

References

Tom M. Apostol, Introduction to analytic number theory, Undergraduate Texts in Mathematics, Springer-Verlag, New York-Heidelberg, 1976. MR 0434929
A. O. L. Atkin and D. J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (2004), no. 246, 1023–1030. MR 2031423, DOI 10.1090/S0025-5718-03-01501-1
Jonathan Bober, Database of zeros of the zeta function, 2014, www.lmfdb.org/zeros/zeta/.
Andrew R. Booker, Artin’s conjecture, Turing’s method, and the Riemann hypothesis, Experiment. Math. 15 (2006), no. 4, 385–407. MR 2293591
J. Büthe, Jens Franke, Alexander Jost, and Thorsten Kleinjung, A practical analytic method for calculating $\pi (x)$, to appear.
Harold Davenport, Multiplicative number theory, 3rd ed., Graduate Texts in Mathematics, vol. 74, Springer-Verlag, New York, 2000. Revised and with a preface by Hugh L. Montgomery. MR 1790423
M. Deléglise and J. Rivat, Computing $\pi (x)$: the Meissel, Lehmer, Lagarias, Miller, Odlyzko method, Math. Comp. 65 (1996), no. 213, 235–245. MR 1322888, DOI 10.1090/S0025-5718-96-00674-6
William Floyd Galway, Analytic computation of the prime-counting function, ProQuest LLC, Ann Arbor, MI, 2004. Thesis (Ph.D.)–University of Illinois at Urbana-Champaign. MR 2706687
J. C. Lagarias and A. M. Odlyzko, Computing $\pi (x)$: an analytic method, J. Algorithms 8 (1987), no. 2, 173–191. MR 890871, DOI 10.1016/0196-6774(87)90037-X
J. C. Lagarias, V. S. Miller, and A. M. Odlyzko, Computing $\pi (x)$: the Meissel-Lehmer method, Math. Comp. 44 (1985), no. 170, 537–560. MR 777285, DOI 10.1090/S0025-5718-1985-0777285-5
D. H. Lehmer, On the exact number of primes less than a given limit, Illinois J. Math. 3 (1959), 381–388. MR 106883
Meissel, Ueber die Bestimmung der Primzahlenmenge innerhalb gegebener Grenzen, Math. Ann. 2 (1870), no. 4, 636–642 (German). MR 1509683, DOI 10.1007/BF01444045
Meissel, Berechnung der Menge von Primzahlen, welche innerhalb der ersten Milliarde natürlicher Zahlen vorkommen, Math. Ann. 25 (1885), no. 2, 251–257 (German). MR 1510308, DOI 10.1007/BF01446409
Ramon E. Moore, Interval analysis, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1966. MR 0231516
David J. Platt, Isolating some non-trivial zeros of zeta, In preparation (2013).
Nathalie Revol and Fabrice Rouillier, A Library for Arbitrary Precision Interval Arithmetic, 10th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics, 2002.
Barkley Rosser, Explicit bounds for some functions of prime numbers, Amer. J. Math. 63 (1941), 211–232. MR 3018, DOI 10.2307/2371291
The Course Team, Complex Analysis Handbook, The Open University, 1994.