Mobius Function

Definition

\[\mu(n) = \begin{cases} 1 & n = 1 \\ 0 & n \text{ has squared prime factors} \\ (-1)^k & \text{where } k \text{ is the count of distinct prime factors of } n \end{cases}\]

Properties

The Mobius function is multilpicative:

\[\sum_{d \mid n} \mu(d) = \varepsilon(n) \\ \mu \ast 1 = \varepsilon\]

where \(\varepsilon(n) = [n = 1]\) and \(\ast\) denotes Dirichlet convolution.

Linear Sieve Copmutation

mobius[1] = 1;
for (int i = 2; i <= limit; i++) {
    if (!composite[i]) {
        primes[++prime_count] = i;
        mobius[i] = -1;
    }
    for (int j = 1; j <= prime_count && primes[j] * i <= limit; j++) {
        composite[primes[j] * i] = true;
        if (i % primes[j] == 0) {
            mobius[primes[j] * i] = 0;
            break;
        } else {
            mobius[primes[j] * i] = -mobius[i];
        }
    }
}

Mobius Inversion

Form 1

\[f(n) = \sum_{d \mid n} g(d) \implies g(n) = \sum_{d \mid n} \mu(d) f\left(\frac{n}{d}\right)\]

Form 2

\[f(n) = \sum_{n \mid d} g(d) \implies g(n) = \sum_{n \mid d} \mu\left(\frac{d}{n}\right) f(d)\]

Example Applications

Interval GCD Counting

\[\sum_{x=1}^a \sum_{y=1}^b [\gcd(x,y) = 1] = \sum_{d=1}^{\min(a,b)} \mu(d) \left\lfloor\frac{a}{d}\right\rfloor \left\lfloor\frac{b}{d}\right\rfloor\]

long long interval_gcd(int a, int b) {
    long long result = 0;
    int bound = min(a, b);
    for (int left = 1, right; left <= bound; left = right + 1) {
        right = min(a/(a/left), b/(b/left));
        result += (mobius_prefix[right] - mobius_prefix[left-1]) * 
                 (long long)(a/left) * (b/left);
    }
    return result;
}

Prime GCD Summation

\[\sum_{p \in \mathbb{P}} \sum_{x=1}^n \sum_{y=1}^m [\gcd(x,y)=p] = \sum_{k=1}^{\min(n,m)} \left\lfloor\frac{n}{k}\right\rfloor \left\lfloor\frac{m}{k}\right\rfloor \sum_{p \mid k, p \in \mathbb{P}} \mu\left(\frac{k}{p}\right)\]

for (int p : primes) {
    for (int k = p; k <= limit; k += p) {
        prime_sum[k] += mobius[k/p];
    }
}

Divisor Function Analysis

\[d(ij) = \sum_{x \mid i} \sum_{y \mid j} [\gcd(x,y)=1] \\ \sum_{i=1}^n \sum_{j=1}^m d(ij) = \sum_{d=1}^{\min(n,m)} \mu(d) \cdot s\left(\left\lfloor\frac{n}{d}\right\rfloor\right) \cdot s\left(\left\lfloor\frac{m}{d}\right\rfloor\right)\]

where \(s(x) = \sum_{k=1}^x \left\lfloor\frac{x}{k}\right\rfloor\)

long long divisor_sum(int n, int m) {
    long long total = 0;
    int bound = min(n, m);
    for (int left = 1, right; left <= bound; left = right + 1) {
        right = min(n/(n/left), m/(m/left));
        total += (mobius_prefix[right] - mobius_prefix[left-1]) * 
                divisor_table[n/left] * divisor_table[m/left];
    }
    return total;
}