Mertens Function

Mertens function can be informally called as the Moebius Summatory function. Well because,

$M(n)=\displaystyle\sum\limits_{k=1}^n\mu(n)$

where $\mu(n)$ is the Mobius function.

Very similar to computation of Totient summatory function is the idea of Merten's function. Like in the case of Totient summatory function, applying A special case of Dirichlet's Hyerbola method  exploits a property of Mobius function, $\mu(n)$. For integer $n$, we have

$\displaystyle\sum\limits_{d|n}\mu(n)=
\begin{cases}
1,&\text{if }n=1\\
0,&\text{if }n>1
\end{cases}$

In other words, $\mu*1=\epsilon$, where $\epsilon$ is the multiplicative identity. (i.e. $\epsilon(1)=1$, all other values $0$).

What this property does is simplify $\hat{F}(n)$ to a incredibly simple value. Let $f(n)=\mu(n)$. Then,

$F(n)=\displaystyle\sum\limits_{i=1}^n\mu(i)=M(n)$ and $\hat{F}(n)=\displaystyle\sum\limits_{i=1}^n\sum_{d|i}\mu(d)=1$

Using these values in A special case of Dirichlet's Hyperbola method, we have

$1=\displaystyle\sum\limits_{i=1}^{n/(u+1)} \left\lfloor\frac{n}{i}\right\rfloor \mu(i) + \sum_{d=1}^u M\left(\left\lfloor\frac{n}{d}\right\rfloor\right) -u^{\text{ }}M\left(\left\lfloor\frac{n}{u+1}\right\rfloor\right)$, $u=\lfloor \sqrt{n}\rfloor$

Solving for the first term of the right summation,

$M(n)=1-\displaystyle\sum\limits_{i=1}^{n/(u+1)} \left\lfloor\frac{n}{i}\right\rfloor \mu(i) - \sum_{d=2}^u M\left(\left\lfloor\frac{n}{d}\right\rfloor\right) +u^{\text{ }}M\left(\left\lfloor\frac{n}{u+1}\right\rfloor\right)$, $u=\lfloor \sqrt{n}\rfloor$

Precomputing the values of $\mu(k)$ for $k \leq \sqrt{n}$ and memoizing, gives a clean method to calculate the Mertens function. Using a similar code, I can computer $M(10^9)=-222$ in $70$ seconds, $M(10^8)=1928$ in $15$ seconds and $M(10^7)=1037$ in $2$ seconds.

Again as in Totient summatory function, we can use the intermediate result we obtained in Dirichlet's hyperbola method to write

$1=\displaystyle\sum\limits_{k=1}^nM\left(\left\lfloor\frac{n}{k}\right\rfloor\right)$

$M(n)=1-\displaystyle\sum\limits_{k=n}^nM\left(\left\lfloor\frac{n}{k}\right\rfloor\right)$

Again this method avoids precomputation at cost of being time-expensive.


Yours Aye
Me