Computing the Mertens function - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T10:30:34Z http://mathoverflow.net/feeds/question/36358 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/36358/computing-the-mertens-function Computing the Mertens function Nameless 2010-08-22T05:11:26Z 2012-05-02T16:15:39Z <p>I wonder if anybody can help me with this problem.</p> <p>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. </p> <p>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.</p> <p>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. </p> <p>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.</p> http://mathoverflow.net/questions/36358/computing-the-mertens-function/36360#36360 Answer by Gjergji Zaimi for Computing the Mertens function Gjergji Zaimi 2010-08-22T06:02:16Z 2010-08-22T06:02:16Z <p><a href="http://projecteuclid.org/DPubS?verb=Display&amp;version=1.0&amp;service=UI&amp;handle=euclid.em/1047565447&amp;page=record" rel="nofollow">This</a> 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 <a href="http://www.unirioja.es/cu/jvarona/downloads/Benito-Varona-TOMATJ-Mertens.pdf" rel="nofollow">this paper</a> to compute things about the Mertens function. <a href="http://www.emis.ams.org/journals/EM/expmath/volumes/13/13.4/Kotnik.pdf" rel="nofollow">This</a> paper seems to claim that these algorithms haven't been improved upon.</p> http://mathoverflow.net/questions/36358/computing-the-mertens-function/95781#95781 Answer by Johan Andersson for Computing the Mertens function Johan Andersson 2012-05-02T16:15:39Z 2012-05-02T16:15:39Z <p>As I indicate in the answer <a href="http://mathoverflow.net/questions/95726/mertens-function-in-time-o-sqrt-x" rel="nofollow">http://mathoverflow.net/questions/95726/mertens-function-in-time-o-sqrt-x</a>, 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.</p>