Computing 𝜓(𝑥)

Deléglise, Marc; Rivat, Joël

doi:10.1090/S0025-5718-98-00977-6

Computing $\psi (x)$
HTML articles powered by AMS MathViewer

by Marc Deléglise and Joël Rivat PDF

Math. Comp. 67 (1998), 1691-1696 Request permission

Abstract:

Let $\Lambda$ denote the Von Mangoldt function and $\psi (x)=\sum _{n \leq x} \Lambda (n)$. 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

M. Deléglise and J. Rivat, Computing the summation of the Möbius function, Experimental Mathematics, 5 (1996), pp. 291–295.
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
D. R. Heath-Brown, Prime numbers in short intervals and a generalized Vaughan identity, Canadian J. Math. 34 (1982), no. 6, 1365–1377. MR 678676, DOI 10.4153/CJM-1982-095-9
G. Hoheisel, Primzahlprobleme in der Analysis, Sitz. Preuss. Akad. Wiss., 33 (1930), pp. 3–11.
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
R. C. Vaughan, An elementary method in prime number theory, Acta Arith. 37 (1980), 111–115. MR 598869, DOI 10.4064/aa-37-1-111-115
Sam Perlis, Maximal orders in rational cyclic algebras of composite degree, Trans. Amer. Math. Soc. 46 (1939), 82–96. MR 15, DOI 10.1090/S0002-9947-1939-0000015-X