MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I wonder if anybody can help me with this problem.

I'm trying to compute the Mertens function for large $n$. The most obvious algorithm is just to compute all primes up to $\sqrt{n}$ and then to sieve. That takes at least an order of $n\log n$ operations, and really even more.

The most recent article that I could find that discusses methods to compute the function directly is dated 1994, and it proposes to do exactly that.

Are there any known algorithms that let you compute Mertens faster than by sieving? I know that $\pi(n)$ can be computed in $O(n^{2/3})$, I looked into that algorithm but it does not seem to be easily adaptable to my task.

Alternatively, I could use an algorithm to compute $M(n+dn)-M(n)$ for $dn\ll n$ (say $dn\sim \sqrt{n}$ ) in $O(\sqrt{n})$ time or less.

share|cite|improve this question
the simplest algorithm is computing $M(\lfloor n/k \rfloor)$ for $k \le n$ so only $M(k)$ and $M(\lfloor n/k \rfloor)$ for $k \le \sqrt{n}$, exploiting $\sum_{k=1}^n M(\lfloor n/k \rfloor) = 1$ – user1952009 Feb 29 at 23:29
up vote 7 down vote accepted

This article presents an algorithm to compute Mertens function in $O(x^{2/3}(\log \log x)^{1/3})$ time and $O(x^{1/3}(\log \log x)^{2/3})$ space, I wonder if it is the same one you are referring to. On the other hand people sometimes make use of certain recursions such as the results in this paper to compute things about the Mertens function. This paper seems to claim that these algorithms haven't been improved upon.

share|cite|improve this answer
Thank you, it should be interesting, I'm going to work through it now. It's not the same article I was referring to, that was <a href="">; this one</a>. – Nameless Aug 22 '10 at 6:39
Hrm, isn't this web site supposed to allow 'a' HTML tags? – Nameless Aug 22 '10 at 6:40
It think it doesn't work in the comments section. – Gjergji Zaimi Aug 22 '10 at 6:49

As I indicate in the answer Mertens' function in time $O(\sqrt x)$, there is a method in Lagarias-Odlyzkos 1987 paper "Computing $\pi(x)$ an analytic method" (which I sketch in that answer) that calculates $M(x)$ on $O(x^{1/2+\epsilon})$ time. The Kotnik-Van de Lune paper that Gjergji Zaimi cites indeed also cites this paper. While the methods that depend on values of the Riemann zeta-function (like the Lagarias-Odlyzko method) might be asymtotically faster, the combinatorial identities are simpler to implement, and might also be faster depending on the ranges of $x$ considered.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.