Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Counting sums of two squares: the Meissel-Lehmer method

Author: P. Shiu
Journal: Math. Comp. 47 (1986), 351-360
MSC: Primary 11Y35; Secondary 11N37, 11P05
MathSciNet review: 842141
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In 1870, E. D. F. Meissel developed a method for computing the individual values of the prime-counting function, and, in 1959, D. H. Lehmer simplified and extended Meissel's method. Let $ W(x)$ count the numbers not exceeding x that are sums of two squares. We develop a variant of the Meissel-Lehmer method for $ W(x)$ and use it to calculate $ W({10^{12}})$.

References [Enhancements On Off] (What's this?)

  • [1] H. Halberstam & H. E. Richert, Sieve Methods, Academic Press, London, 1974. MR 0424730 (54:12689)
  • [2] G. H. Hardy, Ramanujan. Twelve Lectures on Subjects Suggested by His Life and Work, Cambridge Univ. Press, 1940. MR 0004860 (3:71d)
  • [3] L. K. Hua, "The lattice-points in a circle," Quart. J. Math. Oxford, v. 13, 1942, pp. 18-29. MR 0007768 (4:190e)
  • [4] H. B. Keller & J. R. Swenson, "Experiments on the lattice problem of Gauss," Math. Comp., v. 17, 1963, pp. 223-230. MR 0166168 (29:3445)
  • [5] J. C. Lagarias, V. S. Miller & A. M. Odlyzko, "Computing $ \pi (x)$: The Meissel-Lehmer method," Math. Comp., v. 44, 1985, pp. 537-560. MR 777285 (86h:11111)
  • [6] E. Landau, "Über die Einteilung der positiven ganzen Zahlen in vier Klassen nach der Mindestzahl der zu ihrer additiven Zusammensetzung erforderlichen Quadrate," Arch. Math. Phys. (3), v. 13, 1908, pp. 305-312.
  • [7] D. H. Lehmer, "On the exact number of primes less than a given limit," Illinois J. Math., v. 3, 1959, pp. 381-388. MR 0106883 (21:5613)
  • [8] E. D. F. Meissel, "Über die Bestimmung der Primzahlmenge innerhalb gegebener Grenzen," Math. Ann., v. 2, 1870, pp. 636-642. MR 1509683

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y35, 11N37, 11P05

Retrieve articles in all journals with MSC: 11Y35, 11N37, 11P05

Additional Information

Keywords: Meissel-Lehmer method, sums of two squares
Article copyright: © Copyright 1986 American Mathematical Society

American Mathematical Society