Joint with Lola Thompson.

Consider either of two related problems: determining the precise

number $\pi(x)$ of prime numbers $p\leq x$, and computing the Mertens

function $M(x) = \sum_{n\leq x} \mu(n)$, where $\mu$ is the Möbius function.

The two best algorithms known are the following:

An analytic algorithm (Lagarias-Odlyzko, 1987), with computations

based on integrals of $\zeta(s)$; its running time is $O(x^{1/2+\epsilon})$.

A more elementary algorithm (Meissel-Lehmer, 1959 and Lagarias-Miller-Odlyzko,

1985; refined by Del\'eglise-Rivat, 1996), with running time about $O(x^{2/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 $\pi(x)$. Moreover, in the range explored to date ($x\leq 10^{24}$),

the elementary algorithm is faster in practice.

Implementing the analytic algorithm for computing $\sum_{n\leq x} \mu(n)$ is

likely to be at least as technically difficult as for $\pi(x)$.

We present a new elementary algorithm with running time about $O(x^{3/5})$

for computing $M(x) = \sum_{n\leq x} \mu(n)$. The algorithm should be

adaptable to computing $\pi(x)$ and other related problems.

The main idea is to use linear approximations to the function

$(x,y) \mapsto N/x y$ together with Diophantine approximation.

© MPI f. Mathematik, Bonn | Impressum & Datenschutz |