Practical Computations of the Mertens Function: $M(10^{24})$ and $M(10^{25})$

Abstract

The Mertens function is defined as $M(x)={\sum }_{n\le x}\hat{I}¼(n)$, where $\hat{I}¼(n)$ is the Möbius function. This paper describes a practical implementation of the classical $O(x^{2/3+\epsilon })$ algorithm for computing $M(x)$ at isolated values, together with the segmented Möbius and Mertens sieve on which it relies. The implementation was used to compute $M(10^{24})=7189337839$ and $M(10^{25})=-258560632948$, taking $7.0$ days and $34.6$ days, respectively. These computations extend the previous record of $M(10^{23})$ by two orders of magnitude. Run standalone, the segmented sieve computed all Mertens values through $10^{16}$ in approximately $7.4$ days, compared with the $7.5$-month runtime of the author's 2018 computation. In pursuit of the most practical isolated-value method, an optimized implementation of the asymptotically faster Helfgott-Thompson algorithm is also presented, running roughly four times faster than the original implementation. With both implementations optimized, the choice between methods depends on input size and hardware. The contribution is a reproducible computation and implementation study, rather than a new asymptotic algorithm.

31 pages, 3 figures; code available