Summing μ ( n ) : a faster elementary algorithm.

We present a new elementary algorithm that takes time O ϵ x 3 5 ( log x ) 8 5 + ϵ and space O x 3 10 ( log x ) 13 10 (measured bitwise) for computing M ( x ) = ∑ n ≤ x μ ( n ) , where μ ( n ) is the Möbius function. This is the first improvement in the exponent of x for an elementary algorithm since 1985. We also show that it is possible to reduce space consumption to O ( x 1 / 5 ( log x ) 5 / 3 ) by the use of (Helfgott in: Math Comput 89:333-350, 2020), at the cost of letting time rise to the order of x 3 / 5 ( log x ) 2 log log x .