Let $M^*(n)$ be the "odd Mertens function", defined by $M^*(n) = \sum \mu(k)$ for odd $k$, $1 \le k \le n$.

Let $r$ be an odd number. Since $\mu(r)$ is multiplicative, $\mu(2r) = -\mu(r)$ and $\mu(4r) = \mu(8r) = \cdots = 0$.

So splitting $M(n) = \sum_{k=1}^n \mu(k)$, the standard Mertens function, by even and odd $k$, we only need to consider odd $k$ and even $k$ not divisible by 4. This gives the identity $M(n) = M^*(n) - M^*(n/2)$ or equivalently $M^*(n) = M(n) + M^*(n/2)$, so with a sublinear algorithm to calculate the Mertens function we have our odd Mertens function too.

My question: can we calculate $M^*(n)$ directly (without recursion) in sub-linear time?

  • $\begingroup$ The effort to calculate the sum is only halved this way, this does not make the calculation sublinear , if it was not before. $\endgroup$ – Peter Jan 5 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.