Mathematics of Computation

Author(s): Eric Bach; Dominic Klyve; Jonathan P. Sorenson.
Journal: Math. Comp. 78 (2009), 2283-2305.
MSC (2000): Primary 11Y16; Secondary 11Y35, 11N05, 68Q25
Posted: April 3, 2009
Retrieve article in: PDF

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.

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)

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

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
Email: dklyve@carthage.edu

Jonathan P. Sorenson
Affiliation: Computer Science and Software Engineering, Butler University, Indianapolis, Indiana 46208
Email: sorenson@butler.edu

DOI: 10.1090/S0025-5718-09-02249-2
PII: S 0025-5718(09)02249-2
Received by editor(s): June 19, 2008
Received by editor(s) in revised form: November 28, 2008
Posted: 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 of article: Copyright 2009, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS