Efficient Computation of Chebyshev's Psi Function

Abstract

In (analytic) number theory, Chebyshev's psi function sums the logarithms of the largest prime powers below a given parameter. It is known that, asymptotically, psi(N) grows like N. In fact, this statement is equivalent to the Prime Number Theorem. However, precise estimates of values of psi are relatively hard to obtain because of its relationship with primes, which are still somewhat mysterious. We present two algorithms for computing psi(N) using arguments based on recent approaches by Helfgott & Thompson (2023) and by Hirsch, Kessler & Mendlovic (2023) for sums of related arithmetic functions. The former only uses elementary methods and sums certain arithmetic functions in roughly O(N^{3/5}) operations using roughly O(N^{3/10}) memory, while the latter considers basic Fourier theory and runs in roughly O(N^{1/2}) operations using roughly O(N^{1/2}) memory. We also discuss certain details regarding our implementation in C++.