I wonder if anybody can help me with this problem.
I'm trying to compute the Mertens function for large n. $n$. The most obvious algorithm is just to compute all primes up to sqrt(n) $\sqrt{n}$ and then to sieve. That takes at least an order of n log n $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) $\pi(n)$ can be computed in O(n^2/3), $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) $M(n+dn)-M(n)$ for dn < < n $dn\ll n$ (say dn~sqrt(n) $dn\sim \sqrt{n}$ ) in O(sqrt(n)) $O(\sqrt{n})$ time or less.
