Computing prime harmonic sums

Bach, Eric; Klyve, Dominic; Sorenson, Jonathan

doi:10.1090/S0025-5718-09-02249-2

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