Consider either of two related problems: determining the precise number
π(x) of prime numbers up to x, and computing
the Mertens function M(x) =
Σn ≤ x μ(n),
where μ is the Möbius function.
The two best algorithms known are the following:
1) An analytic algorithm (Lagarias-Odlyzko, 1987), with computations based on
integrals of ζ(s); its running time is O(x1/2 +
ε).
2) A more elementary algorithm (Meissel-Lehmer, 1959 and
Lagarias-Miller-Odlyzko, 1985; refined by Deléglise-Rivat, 1996),
with running time about O(x2/3).
The analytic algorithm had to wait for almost 30 years to receive its first
rigorous, unconditional implementation (Platt), which
concerns only the computation of π(x). Moreover, in the range
explored to date (x ≤ 1024), the elementary algorithm is
faster in
practice. We present a new elementary algorithm with running time about
O(x3/5) for computing M(x). The algorithm
should be
adaptable to computing π(x) and other related problems.
This talk is based on joint work with Harald Andrés Helfgott.