Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Computing prime harmonic sums

Authors: Eric Bach, Dominic Klyve and Jonathan P. Sorenson
Journal: Math. Comp. 78 (2009), 2283-2305
MSC (2000): Primary 11Y16; Secondary 11Y35, 11N05, 68Q25
Published electronically: April 3, 2009
MathSciNet review: 2521290
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. M. Abramowitz and I. Stegun.
    Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables.
    Dover Publications, 9th printing, 1972. MR 1225604 (94b:00012)
  • 2. M. Agrawal, N. Kayal, and N. Saxena.
    PRIMES is in P.
    Ann. of Math. (2)160:781-793, 2004. MR 2123939 (2006a:11170)
  • 3. G. E. Andrews, R. Askey, and R. Roy.
    Special Functions.
    Cambridge Univ. Press, 1999. MR 1688958 (2000g:33001)
  • 4. E. Bach.
    The complexity of number-theoretic constants,
    Inform. Proc. Lett., 62:145-152, 1997. MR 1453698 (98g:11148)
  • 5. R. P. Brent.
    The first occurrence of large gaps between successive primes.
    Math. Comp., 27(124):959-963, 1973. MR 0330021 (48:8360)
  • 6. R. P. Brent.
    Fast multiple-precision evaluation of elementary functions.
    J. Assoc. Comput. Mach., 23(2):242-251, 1976. MR 0395314 (52:16111)
  • 7. T. J. Dekker.
    A floating-point technique for extending the available precision.
    Numer. Math., 18, 224-242, 1971. MR 0299007 (45:8056)
  • 8. M. Deléglise and J. Rivat.
    Computing $ \pi(x)$: The Meissel, Lehmer, Lagarias, Miller, Odlyzko method.
    Math. Comp., 65(213):235-245, 1996. MR 1322888 (96d:11139)
  • 9. 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.
  • 10. M. Fredman.
    The complexity of maintaining an array and computing its partial sums.
    J. Assoc. Comput. Mach., 29(1):250-260, 1982. MR 662621 (83i:68068)
  • 11. W. F. Galway.
    Robert Bennion's ``Hopping Sieve.''
    In Algorithmic Number Theory (Portland, 1998), volume 1423 of Lecture Notes in Comput. Sci., pages 169-178. Springer, Berlin, 2000. MR 1726069 (2000m:11124)
  • 12. W. F. Galway.
    Dissecting a sieve to cut its need for space.
    In Algorithmic Number Theory (Leiden, 2000), volume 1838 of Lecture Notes in Comput. Sci., pages 297-312. Springer, Berlin, 2000. MR 1850613 (2002g:11176)
  • 13. E. Grosswald.
    Arithmetical functions with periodic zeros.
    Acta Arith., 28(1):1-21, 1975/76. MR 0404172 (53:7975)
  • 14. R. W. Hamming.
    Numerical Methods for Scientists and Engineers.
    Dover, 1986. MR 951632 (89h:65002)
  • 15. E. A. Karatsuba,
    Fast evaluation of transcendental functions.
    Prob. Inform. Trans. 27(4):339-360, 1991. MR 1156939 (93c:65027)
  • 16. D. E. Knuth.
    The Art of Computer Programming: Volume 1, Fundamental Algorithms, 3rd edition,
    Addison-Wesley, 1997. MR 0378456 (51:14624)
  • 17. D. E. Knuth and T. J. Buckholtz,
    Computation of tangent, Euler, and Bernoulli numbers.
    Math. Comp. 21:663-688, 1967. MR 0221735 (36:4787)
  • 18. D. Klyve.
    Explicit Bounds on Twin Primes and Brun's Constant.
    Dissertation, Dartmouth College, 2007.
  • 19. J. C. Lagarias, V. S. Miller, and A. M. Odlyzko.
    Computing $ \pi(x)$: The Meissel-Lehmer method.
    Math. Comp., 44(170):537-560, 1985. MR 777285 (86h:11111)
  • 20. J. C. Lagarias and A. M. Odlyzko.
    Computing $ \pi(x)$: An analytic method.
    J. Algorithms, 8(2):173-191, 1987. MR 890871 (88k:11095)
  • 21. E. Landau.
    Handbuch der Lehre von der Verteilung der Primzahlen. 2 Bände.
    Chelsea Publishing Co., New York, 1953.
    2d ed, With an appendix by Paul T. Bateman. MR 0068565 (16:904d)
  • 22. D. H. Lehmer.
    The exact number of primes less than a given limit.
    Illinois J. Math. 3:381-388, 1959. MR 0106883 (21:5613)
  • 23. D. H. Lehmer.
    Euler constants for arithmetical progressions.
    Acta Arithmetica, 27:125-142, 1975. MR 0369233 (51:5468)
  • 24. 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.
  • 25. S. Linnainmaa.
    Software for doubled-precision floating-point computations.
    ACM Trans. Math. Soft. 7:272-283, 1981. MR 630437 (82h:68041)
  • 26. E. D. F. Meissel.
    Ueber die Bestimmung der Primzahlenmenge innerhalb gegebener Grenzen.
    Math. Ann., 2:636-642, 1870. MR 1509683
  • 27. T. Oliveira y Silva.
    Fast implementation of the segmented sieve of Eratosthenes.
    Manuscript, 2005.
  • 28. K. Prachar.
    Über die kleinste quadratfreie Zahl einer arithmetischen Reihe.
    Monat. Math. 62:173-176, 1958. MR 0092806 (19:1160g)
  • 29. D. M. Priest,
    Algorithms for arbitrary precision floating point arithmetic.
    Proc. 10th IEEE Symp. Computer Arithmetic, IEEE Press, 1991.
  • 30. L. Schoenfeld.
    Sharper bounds for the Chebyshev functions $ \theta(x)$ and $ \psi(x)$. II.
    Math. Comp., 30(134):337-360, 1976. MR 0457374 (56:15581b)
  • 31. J. P. Sorenson.
    The pseudosquares prime sieve.
    In Florian Hess, Sebastian Pauli, and Michael Pohst, editors, Proceedings of the 7th International Symposium on Algorithmic Number Theory (ANTS-VII), pages 193-207, Berlin, Germany, July 2006. Springer.
    Lecture Notes in Comput. Sci., 4076, ISBN 3-540-36075-1. MR 2282925 (2007m:11168)
  • 32. V. Shoup.
    NTL: A library for doing number theory.
    Software and documentation available on the author's home page, CS Dept., New York University.
  • 33. D. V. Widder,
    The Laplace Transform.
    Princeton Univ. Press, 1941. MR 0005923 (3:232d)
  • 34. E. T. Whittaker and G. N. Watson.
    A Course of Modern Analysis.
    Cambridge Univ. Press, 1927. MR 1424469 (97k:01072)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y16, 11Y35, 11N05, 68Q25

Retrieve articles in all journals with MSC (2000): 11Y16, 11Y35, 11N05, 68Q25

Additional Information

Eric Bach
Affiliation: Computer Sciences Department, University of Wisconsin-Madison, 1210 W. Dayton Street, Madison, Wisconsin 53706

Dominic Klyve
Affiliation: Department of Mathematics, Carthage College, 2001 Alford Drive, Kenosha, Wisconsin 53140

Jonathan P. Sorenson
Affiliation: Computer Science and Software Engineering, Butler University, Indianapolis, Indiana 46208

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.
Article copyright: © Copyright 2009 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.