Computing prime harmonic sums
HTML articles powered by AMS MathViewer
- by Eric Bach, Dominic Klyve and Jonathan P. Sorenson;
- Math. Comp. 78 (2009), 2283-2305
- DOI: https://doi.org/10.1090/S0025-5718-09-02249-2
- Published electronically: April 3, 2009
- PDF | 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 378456
- 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 68565
- 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, NJ, 1941. MR 5923
- 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
Bibliographic 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