Mertens Function

The summary function

$$M(n)\equiv \sum_{k=1}^n \mu(k)= {6\over \pi^2} n+{\mathcal O}(\sqrt{n}\,),$$

where $\mu(n)$ is the Möbius Function. The first few values are 1, 0, $-1$, $-1$, $-2$, $-1$, $-2$, $-2$, $-2$, $-1$, $-2$, $-2$, ... (Sloane's A002321). The first few values of $n$ at which $M(n)=0$ are 2, 39, 40, 58, 65, 93, 101, 145, 149, 150, ... (Sloane's A028442).

Mertens function obeys

$$\sum_{n=1}^x M\left({x\over n}\right)=1$$

(Lehman 1960). The analytic form is unsolved, although Mertens Conjecture that

$$\vert M(x)\vert<x^{1/2}$$

has been disproved.

Lehman (1960) gives an algorithm for computing $M(x)$ with ${\mathcal O}(x^{2/3+\epsilon})$ operations, while the Lagarias-Odlyzko (1987) algorithm for computing the Prime Counting Function $\pi(x)$ can be modified to give $M(x)$ in ${\mathcal O}(x^{3/5+\epsilon})$ operations.

See also Mertens Conjecture, Möbius Function

References

Lagarias, J. and Odlyzko, A. ``Computing $\pi(x)$: An Analytic Method.'' J. Algorithms 8, 173-191, 1987.

Lehman, R. S. ``On Liouville's Function.'' Math. Comput. 14, 311-320, 1960.

Odlyzko, A. M. and te Riele, H. J. J. ``Disproof of the Mertens Conjecture.'' J. reine angew. Math. 357, 138-160, 1985.

Sloane, N. J. A. Sequences A028442 and A002321/M0102 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.