Computing 𝜋(𝑥) analytically

Platt, David

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

Computing $\pi(x)$ analytically

Author: David J. Platt
Journal: Math. Comp. 84 (2015), 1521-1535
MSC (2010): Primary 11Y35; Secondary 11N37, 11N56, 11Y70
DOI: https://doi.org/10.1090/S0025-5718-2014-02884-6
Published electronically: October 3, 2014
MathSciNet review: 3315519
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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}$ .

[1] Tom M. Apostol, Introduction to analytic number theory, Springer-Verlag, New York-Heidelberg, 1976. Undergraduate Texts in Mathematics. MR 0434929
[2] A. O. L. Atkin and D. J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (2004), no. 246, 1023–1030. MR 2031423, https://doi.org/10.1090/S0025-5718-03-01501-1
[3] Jonathan Bober, Database of zeros of the zeta function, 2014, www.lmfdb.org/zeros/zeta/.
[4] Andrew R. Booker, Artin’s conjecture, Turing’s method, and the Riemann hypothesis, Experiment. Math. 15 (2006), no. 4, 385–407. MR 2293591
[5] J. Büthe, Jens Franke, Alexander Jost, and Thorsten Kleinjung, A practical analytic method for calculating $\pi (x)$ , to appear.
[6] 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
[7] M. Deléglise and J. Rivat, Computing 𝜋(𝑥): the Meissel, Lehmer, Lagarias, Miller, Odlyzko method, Math. Comp. 65 (1996), no. 213, 235–245. MR 1322888, https://doi.org/10.1090/S0025-5718-96-00674-6
[8] 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
[9] J. C. Lagarias and A. M. Odlyzko, Computing 𝜋(𝑥): an analytic method, J. Algorithms 8 (1987), no. 2, 173–191. MR 890871, https://doi.org/10.1016/0196-6774(87)90037-X
[10] J. C. Lagarias, V. S. Miller, and A. M. Odlyzko, Computing 𝜋(𝑥): the Meissel-Lehmer method, Math. Comp. 44 (1985), no. 170, 537–560. MR 777285, https://doi.org/10.1090/S0025-5718-1985-0777285-5
[11] D. H. Lehmer, On the exact number of primes less than a given limit, Illinois J. Math. 3 (1959), 381–388. MR 0106883
[12] Meissel, Ueber die Bestimmung der Primzahlenmenge innerhalb gegebener Grenzen, Math. Ann. 2 (1870), no. 4, 636–642 (German). MR 1509683, https://doi.org/10.1007/BF01444045
[13] 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, https://doi.org/10.1007/BF01446409
[14] Ramon E. Moore, Interval analysis, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1966. MR 0231516
[15] David J. Platt, Isolating some non-trivial zeros of zeta, In preparation (2013).
[16] 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.
[17] Barkley Rosser, Explicit bounds for some functions of prime numbers, Amer. J. Math. 63 (1941), 211–232. MR 0003018, https://doi.org/10.2307/2371291
[18] The Course Team, Complex Analysis Handbook, The Open University, 1994.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y35, 11N37, 11N56, 11Y70

Retrieve articles in all journals with MSC (2010): 11Y35, 11N37, 11N56, 11Y70

Additional Information

David J. Platt
Affiliation: Heilbronn Institute for Mathematical Research, University of Bristol
Email: dave.platt@bris.ac.uk

DOI: https://doi.org/10.1090/S0025-5718-2014-02884-6
Received by editor(s): March 26, 2012
Received by editor(s) in revised form: September 4, 2013
Published electronically: October 3, 2014
Additional Notes: This work formed part of the author’s Ph.D. research and he would like to thank Dr. Andrew Booker for his patient supervision. Funding was provided by the Engineering and Physical Sciences Research Council through the University of Bristol and he is grateful to both.
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.