# Odd Mertens function

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?

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