## Computing prime harmonic sums

HTML articles powered by AMS MathViewer

- by Eric Bach, Dominic Klyve and Jonathan P. Sorenson PDF
- Math. Comp.
**78**(2009), 2283-2305 Request permission

## Abstract:

We discuss a method for computing $\sum _{p \le x} 1/p$, using time about $x^{2/3}$ and space about $x^{1/3}$. It is based on the Meissel-Lehmer algorithm for computing the prime-counting function $\pi (x)$, which was adapted and improved by Lagarias, Miller, and Odlyzko. We used this algorithm to determine the first point at which the prime harmonic sum first crosses 4.## References

- Milton Abramowitz and Irene A. Stegun (eds.),
*Handbook of mathematical functions with formulas, graphs, and mathematical tables*, Dover Publications, Inc., New York, 1992. Reprint of the 1972 edition. MR**1225604** - Manindra Agrawal, Neeraj Kayal, and Nitin Saxena,
*PRIMES is in P*, Ann. of Math. (2)**160**(2004), no. 2, 781–793. MR**2123939**, DOI 10.4007/annals.2004.160.781 - George E. Andrews, Richard Askey, and Ranjan Roy,
*Special functions*, Encyclopedia of Mathematics and its Applications, vol. 71, Cambridge University Press, Cambridge, 1999. MR**1688958**, DOI 10.1017/CBO9781107325937 - Eric Bach,
*The complexity of number-theoretic constants*, Inform. Process. Lett.**62**(1997), no. 3, 145–152. MR**1453698**, DOI 10.1016/S0020-0190(97)00051-3 - Richard P. Brent,
*The first occurrence of large gaps between successive primes*, Math. Comp.**27**(1973), 959–963. MR**330021**, DOI 10.1090/S0025-5718-1973-0330021-0 - Richard P. Brent,
*Fast multiple-precision evaluation of elementary functions*, J. Assoc. Comput. Mach.**23**(1976), no. 2, 242–251. MR**395314**, DOI 10.1145/321941.321944 - T. J. Dekker,
*A floating-point technique for extending the available precision*, Numer. Math.**18**(1971/72), 224–242. MR**299007**, DOI 10.1007/BF01397083 - 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 - P. Dusart. Sharper bounds for $\psi , \theta , \pi , p_k$.
*Rapport de recherche #1998-06, Laboratoire d’Arithmétique de Calcul Formel et d’Optimisation*, Univ. Limoges, 1998. - Michael L. Fredman,
*The complexity of maintaining an array and computing its partial sums*, J. Assoc. Comput. Mach.**29**(1982), no. 1, 250–260. MR**662621**, DOI 10.1145/322290.322305 - William F. Galway,
*Robert Bennion’s “hopping sieve”*, Algorithmic number theory (Portland, OR, 1998) Lecture Notes in Comput. Sci., vol. 1423, Springer, Berlin, 1998, pp. 169–178. MR**1726069**, DOI 10.1007/BFb0054860 - William F. Galway,
*Dissecting a sieve to cut its need for space*, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 297–312. MR**1850613**, DOI 10.1007/10722028_{1}7 - Emil Grosswald,
*Arithmetical functions with periodic zeros*, Acta Arith.**28**(1975/76), no. 1, 1–21. MR**404172**, DOI 10.4064/aa-28-1-1-21 - R. W. Hamming,
*Numerical methods for scientists and engineers*, 2nd ed., Dover Publications, Inc., New York, 1986. MR**951632** - E. A. Karatsuba,
*Fast computations of transcendental functions*, Problemy Peredachi Informatsii**27**(1991), no. 4, 76–99 (Russian); English transl., Problems Inform. Transmission**27**(1991), no. 4, 339–360 (1992). MR**1156939** - Donald E. Knuth,
*The art of computer programming*, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms. MR**0378456** - Donald E. Knuth and Thomas J. Buckholtz,
*Computation of tangent, Euler, and Bernoulli numbers*, Math. Comp.**21**(1967), 663–688. MR**221735**, DOI 10.1090/S0025-5718-1967-0221735-9 - D. Klyve.
*Explicit Bounds on Twin Primes and Brun’s Constant*. Dissertation, Dartmouth College, 2007. - 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 - 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 - Edmund Landau,
*Handbuch der Lehre von der Verteilung der Primzahlen. 2 Bände*, Chelsea Publishing Co., New York, 1953 (German). 2d ed; With an appendix by Paul T. Bateman. MR**0068565** - D. H. Lehmer,
*On the exact number of primes less than a given limit*, Illinois J. Math.**3**(1959), 381–388. MR**106883**, DOI 10.1215/ijm/1255455259 - D. H. Lehmer,
*Euler constants for arithmetical progressions*, Acta Arith.**27**(1975), 125–142. MR**369233**, DOI 10.4064/aa-27-1-125-142 - X. S. Li, J. W. Demmel, D. H. Bailey, G. Henry, Y. Hida, J. Iskandar, W. Kahan, S. Y. Kang, A. Kapur, M. C. Martin, B. J. Thompson, T. Tung, and D. J. Yoo. Design, implementation, and testing of extended and mixed precision BLAS.
*ACM Trans. Math. Soft.*, 28:152–205, 2002. - Seppo Linnainmaa,
*Software for doubled-precision floating-point computations*, ACM Trans. Math. Software**7**(1981), no. 3, 272–283. MR**630437**, DOI 10.1145/355958.355960 - Meissel,
*Ueber die Bestimmung der Primzahlenmenge innerhalb gegebener Grenzen*, Math. Ann.**2**(1870), no. 4, 636–642 (German). MR**1509683**, DOI 10.1007/BF01444045 - T. Oliveira y Silva. Fast implementation of the segmented sieve of Eratosthenes. Manuscript, 2005.
- Karl Prachar,
*Über die kleinste quadratfreie Zahl einer arithmetischen Reihe*, Monatsh. Math.**62**(1958), 173–176 (German). MR**92806**, DOI 10.1007/BF01301288 - D. M. Priest, Algorithms for arbitrary precision floating point arithmetic.
*Proc. 10th IEEE Symp. Computer Arithmetic*, IEEE Press, 1991. - J. Barkley Rosser and Lowell Schoenfeld,
*Sharper bounds for the Chebyshev functions $\theta (x)$ and $\psi (x)$*, Math. Comp.**29**(1975), 243–269. MR**457373**, DOI 10.1090/S0025-5718-1975-0457373-7 - Jonathan P. Sorenson,
*The pseudosquares prime sieve*, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 4076, Springer, Berlin, 2006, pp. 193–207. MR**2282925**, DOI 10.1007/11792086_{1}5 - V. Shoup. NTL: A library for doing number theory. Software and documentation available on the author’s home page, CS Dept., New York University.
- David Vernon Widder,
*The Laplace Transform*, Princeton Mathematical Series, vol. 6, Princeton University Press, Princeton, N. J., 1941. MR**0005923** - E. T. Whittaker and G. N. Watson,
*A course of modern analysis*, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1996. An introduction to the general theory of infinite processes and of analytic functions; with an account of the principal transcendental functions; Reprint of the fourth (1927) edition. MR**1424469**, DOI 10.1017/CBO9780511608759

## Additional Information

**Eric Bach**- Affiliation: Computer Sciences Department, University of Wisconsin-Madison, 1210 W. Dayton Street, Madison, Wisconsin 53706
- Email: bach@cs.wisc.edu
**Dominic Klyve**- Affiliation: Department of Mathematics, Carthage College, 2001 Alford Drive, Kenosha, Wisconsin 53140
- MR Author ID: 776121
- Email: dklyve@carthage.edu
**Jonathan P. Sorenson**- Affiliation: Computer Science and Software Engineering, Butler University, Indianapolis, Indiana 46208
- MR Author ID: 334195
- Email: sorenson@butler.edu
- Received by editor(s): June 19, 2008
- Received by editor(s) in revised form: November 28, 2008
- Published electronically: April 3, 2009
- Additional Notes: E. Bach was supported by NSF grants CCR-0523680, CCF-0635355, and a Vilas Associate Award from the Wisconsin Alumni Research Foundation.

D. Klyve was supported by NSF grant DMS-0401422

J. P. Sorenson was supported by a grant from the Holcomb Awards Committee

A preliminary version of this work was presented as a poster at ANTS-VII in Berlin, Germany, July 2006. - © Copyright 2009
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp.
**78**(2009), 2283-2305 - MSC (2000): Primary 11Y16; Secondary 11Y35, 11N05, 68Q25
- DOI: https://doi.org/10.1090/S0025-5718-09-02249-2
- MathSciNet review: 2521290