Problem 974: Mobius Function Partial Sums

Mathematical Foundation

Definition 1 (Mobius Function). For $n \in \mathbb{Z}_{>0}$:

Theorem 1 (Mobius Inversion Formula). If $f(n) = \sum_{d \mid n} g(d)$ for all $n \ge 1$, then $g(n) = \sum_{d \mid n} \mu(n/d)\, f(d)$.

Proof. We verify:

Setting $d = e\ell$, the inner sum becomes $\sum_{\ell \mid (n/e)} \mu(n/(e\ell))= \sum_{m \mid (n/e)} \mu(m) = [n/e = 1] = [n = e]$, using the fundamental identity $\sum_{d \mid k} \mu(d) = [k=1]$. Hence the double sum equals $g(n)$. $\square$

Theorem 2 (Fundamental Identity of $\mu$). For all $n \ge 1$, $\sum_{d \mid n} \mu(d) = [n = 1]$.

Proof. For $n = 1$, the sum is $\mu(1) = 1$. For $n > 1$, write $n = p_1^{a_1} \cdots p_r^{a_r}$. Then $\sum_{d \mid n} \mu(d) = \sum_{S \subseteq \{p_1,\ldots,p_r\}} (-1)^{|S|} = (1-1)^r = 0$, since only squarefree divisors contribute. $\square$

Theorem 3 (Mertens Function and the Riemann Hypothesis). The Riemann Hypothesis is equivalent to the assertion that $M(n) = O(n^{1/2+\varepsilon})$ for every $\varepsilon > 0$.

Proof. (Sketch.) The Dirichlet series $\sum_{n=1}^\infty \mu(n)/n^s = 1/\zeta(s)$ converges for $\Re(s) > 1$. By Perron’s formula, $M(x) = \frac{1}{2\pi i}\int_{c-i\infty}^{c+i\infty} \frac{x^s}{s\,\zeta(s)}\,ds$. The poles of $1/\zeta(s)$ correspond to zeros of $\zeta(s)$. If all nontrivial zeros satisfy $\Re(\rho) = 1/2$, the residue contributions give $M(x) = O(x^{1/2+\varepsilon})$. Conversely, if $M(x) = O(x^{1/2+\varepsilon})$ for all $\varepsilon > 0$, then $1/\zeta(s)$ converges for $\Re(s) > 1/2$, implying $\zeta(s) \neq 0$ there. $\square$

Lemma 1 (Computing $\mu$ via Sieve). The Mobius function can be computed for all $n \le N$ in $O(N \log\log N)$ time using a modified Sieve of Eratosthenes that tracks the smallest prime factor and squarefree status.

Proof. Initialize $\mu(1) = 1$. For each prime $p$ found by the sieve, for each multiple $m = p, 2p, 3p, \ldots$: if $p^2 \mid m$, set $\mu(m) = 0$; otherwise, multiply $\mu(m)$ by $-1$. This correctly computes $\mu$ since $\mu$ is multiplicative and $\mu(p^a) = -1$ if $a = 1$, $0$ if $a \ge 2$. The sieve visits each multiple of each prime, totaling $O(\sum_{p \le N} N/p) = O(N \log\log N)$. $\square$

Editorial

Compute the sum of |M(n)| for n = 1 to 10^5, where M(n) = sum_{k=1}^{n} mu(k) is the Mertens function. We compute mu via sieve. Finally, compute prefix sums and accumulate |M(n)|.

Pseudocode

Compute mu via sieve
Compute prefix sums and accumulate |M(n)|

Complexity Analysis

• Time: $O(N \log\log N)$ for the Mobius sieve, plus $O(N)$ for the accumulation loop. Total: $O(N \log\log N)$.
• Space: $O(N)$ for the arrays $\mu$ and is_composite.

Answer

#include <bits/stdc++.h>
using namespace std;
int main() {
    const int N = 100000;
    vector<int> mu(N+1,0); mu[1]=1;
    vector<bool> is_p(N+1,true); vector<int> primes;
    for(int i=2;i<=N;i++){
        if(is_p[i]){primes.push_back(i);mu[i]=-1;}
        for(int p:primes){
            if((long long)i*p>N)break;
            is_p[i*p]=false;
            if(i%p==0){mu[i*p]=0;break;}
            else mu[i*p]=-mu[i];
        }
    }
    long long M=0, ans=0;
    for(int n=1;n<=N;n++){M+=mu[n]; ans+=abs(M);}
    cout<<ans<<endl;
    return 0;
}

"""
Problem 974: Mobius Function Partial Sums

Compute the sum of |M(n)| for n = 1 to 10^5, where M(n) = sum_{k=1}^{n} mu(k)
is the Mertens function.

Key results:
    - mu(n) is the Mobius function: mu(1)=1, mu(n)=0 if n has squared factor,
      mu(n)=(-1)^k if n is product of k distinct primes
    - M(n) = sum of mu(1..n) is the Mertens function
    - The Mertens conjecture |M(n)| < sqrt(n) was disproved but holds for small n
    - answer = sum of |M(n)| for n = 1..10^5

Methods:
    1. linear_sieve_mobius  — compute mu(n) via linear sieve
    2. mertens_function     — prefix sums to get M(n)
    3. mobius_distribution   — count of mu(n) = -1, 0, +1
    4. mertens_vs_sqrt_bound — compare |M(n)| against sqrt(n)
"""

from collections import Counter

def linear_sieve_mobius(N):
    """Compute mu[0..N] using a linear sieve. Returns (mu, primes)."""
    mu = [0] * (N + 1)
    mu[1] = 1
    is_prime = [True] * (N + 1)
    primes = []
    for i in range(2, N + 1):
        if is_prime[i]:
            primes.append(i)
            mu[i] = -1
        for p in primes:
            if i * p > N:
                break
            is_prime[i * p] = False
            if i % p == 0:
                mu[i * p] = 0
                break
            else:
                mu[i * p] = -mu[i]
    return mu, primes

def mertens_function(mu, N):
    """Compute M[0..N] where M[n] = sum mu[1..n]."""
    M = [0] * (N + 1)
    for n in range(1, N + 1):
        M[n] = M[n - 1] + mu[n]
    return M

def mobius_distribution(mu, N):
    """Count occurrences of mu(n) = -1, 0, +1 for n = 1..N."""
    counts = Counter(mu[n] for n in range(1, N + 1))
    return counts

def mertens_vs_sqrt(M, N, step=10):
    """Compute |M(n)| / sqrt(n) at sampled points."""
    ns = list(range(step, N + 1, step))
    ratios = [abs(M[n]) / (n ** 0.5) for n in ns]
    return ns, ratios

#  Verification
# Known: mu(1)=1, mu(2)=-1, mu(3)=-1, mu(4)=0, mu(5)=-1, mu(6)=1
# M(1)=1, M(2)=0, M(3)=-1, M(4)=-1, M(5)=-2, M(6)=-1
_mu, _ = linear_sieve_mobius(10)
assert _mu[1] == 1
assert _mu[2] == -1
assert _mu[3] == -1
assert _mu[4] == 0
assert _mu[5] == -1
assert _mu[6] == 1
_M = mertens_function(_mu, 10)
assert _M[1] == 1
assert _M[6] == -1

#  Main computation
N = 10 ** 5
mu, primes = linear_sieve_mobius(N)
M = mertens_function(mu, N)
answer = sum(abs(M[n]) for n in range(1, N + 1))
print(answer)

#  Visualization — 4-panel figure