Computing the Summation of the Möbius Function

Joël Rivat

Abstract

We describe an elementary method for computing isolated values of M(x) = ∑_{n≤x} μ(n), where μ is the Möbius function. 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. Certain values of M(x) for x up to 10^{16} are listed: for instance, M(10^{16}) = −3195437.