Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

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


References [Enhancements On Off] (What's this?)

  • [1] Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, New York, 1976. Undergraduate Texts in Mathematics. MR 0434929 (55 #7892)
  • [2] Arthur O. L. Atkin and Daniel J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (2004), no. 246, 1023-1030 (electronic). MR 2031423 (2004i:11147), 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 (2007k:11084)
  • [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 (2001f:11001)
  • [7] Marc Deléglise and Joël Rivat, Computing $ \pi (x)$: the Meissel, Lehmer, Lagarias, Miller, Odlyzko method, Math. Comp. 65 (1996), no. 213, 235-245. MR 1322888 (96d:11139), 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] Jeffrey C. Lagarias and Andrew M. Odlyzko, Computing $ \pi (x)$: an analytic method, J. Algorithms 8 (1987), no. 2, 173-191. MR 890871 (88k:11095), https://doi.org/10.1016/0196-6774(87)90037-X
  • [10] Jeffrey C. Lagarias, Victor S. Miller, and Andrew M. Odlyzko, Computing $ \pi (x)$: the Meissel-Lehmer method, Math. Comp. 44 (1985), no. 170, 537-560. MR 777285 (86h:11111), https://doi.org/10.2307/2007973
  • [11] Derrick H. Lehmer, On the exact number of primes less than a given limit, Illinois J. Math. 3 (1959), 381-388. MR 0106883 (21 #5613)
  • [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 (37 #7069)
  • [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 (2,150e)
  • [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.

American Mathematical Society