Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Computing $\psi(x)$


Authors: Marc Deléglise and Joël Rivat
Journal: Math. Comp. 67 (1998), 1691-1696
MSC (1991): Primary 11Y70, 11N56
DOI: https://doi.org/10.1090/S0025-5718-98-00977-6
MathSciNet review: 1474649
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $\Lambda$ denote the Von Mangoldt function and $ \begin{displaystyle} \psi(x)=\sum _{n \leq x} \Lambda(n) \end{displaystyle}$. We describe an elementary method for computing isolated values of $\psi(x)$. The complexity of the algorithm is $O(x^{2/3}(\log\log x)^{1/3})$ time and $O(x^{1/3}(\log\log x)^{2/3})$ space. A table of values of $\psi(x)$ for $x$ up to $10^{15}$ is included, and some times of computation are given.


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

  • 1. M. DELGLISE AND J. RIVAT, Computing the summation of the Möbius function, Experimental Mathematics, 5 (1996), pp. 291-295. CMP 97:09
  • 2. height 2pt depth -1.6pt width 23pt, Computing $\pi(x)$: The Meissel, Lehmer, Lagarias, Miller, Odlyzko method, Mathematics of Computation, 65 (1996), pp. 235-245. MR 96d:11139
  • 3. D. R. HEATH-BROWN, Prime numbers in short intervals and a generalized Vaughan identity, Can.J.Math., 34 (1982), pp. 1365-1377. MR 84g:10075
  • 4. G. HOHEISEL, Primzahlprobleme in der Analysis, Sitz. Preuss. Akad. Wiss., 33 (1930), pp. 3-11.
  • 5. J. LAGARIAS, V. MILLER, AND A. ODLYZKO, Computing $\pi(x)$: The Meissel Lehmer Method, Mathematics of Computation, 44 (1985), pp. 537-560. MR 86h:11111
  • 6. J. LAGARIAS AND A. ODLYZKO, Computing $\pi(x)$: An Analytic Method, Journal of Algorithms, 8 (1987), pp. 173-191. MR 88k:11095
  • 7. R. C. VAUGHAN, An elementary method in prime number theory, Acta Arithmetica, 37 (1980), pp. 111-115. MR 82c:10055
  • 8. I. M. VINOGRADOV, The method of trigonometrical sums in the theory of numbers, translated from the Russian, revised and annotated by K.F. Roth and A. Davenport, Interscience, London, 1954. MR 15,941b

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11Y70, 11N56

Retrieve articles in all journals with MSC (1991): 11Y70, 11N56


Additional Information

Marc Deléglise
Affiliation: Institut Girard Desargues, UPRES-A 5028 Mathematiques, Université Lyon I, 69622 Villeurbanne Cedex, France
Email: deleglis@desargues.univ-lyon1.fr

Joël Rivat
Affiliation: Institut Girard Desargues, UPRES-A 5028 Mathematiques, Université Lyon I, 69622 Villeurbanne Cedex, France
Email: rivat@desargues.univ-lyon1.fr

DOI: https://doi.org/10.1090/S0025-5718-98-00977-6
Received by editor(s): January 23, 1997
Article copyright: © Copyright 1998 American Mathematical Society

American Mathematical Society