Project Euler

Multidimensional Sieve

The Mobius function mu(n) and Mobius inversion extend to multiple dimensions. Given an arithmetic function f(n_1,..., n_k), compute its Mobius inversion efficiently.

Source sync Apr 19, 2026

Problem #0888

Level Level 34

Solved By 221

Languages C++, Python

Answer 227429102

Length 301 words

number_theorylinear_algebramodular_arithmetic

Two players play a game with a number of piles of stones, alternating turns. Each turn a player can choose to remove 1, 2, 4, or 9 stones from a single pile; or alternatively they can choose to split a pile containing two or more stones into two non-empty piles. The winner is the player who removes the last stone.

A collection of piles is called a losing position if the player to move cannot force a win with optimal play. Define $S(N, m)$ to be the number of distinct losing positions arising from $m$ piles of stones where each pile contains from $1$ to $N$ stones. Two positions are considered equivalent if they consist of the same pile sizes. That is, the order of the piles does not matter.

You are given $S(12,4)=204$ and $S(124,9)=2259208528408$.

Find $S(12491249,1249)$. Give your answer modulo $912491249$.

Problem 888: Multidimensional Sieve

Mathematical Analysis

Theorem 1 (Mobius Inversion, 1D)

If $g(n) = \sum_{d \mid n} f(d)$ , then $f(n) = \sum_{d \mid n} \mu(n/d) g(d)$ .

Proof. $\sum_{d \mid n} \mu(n/d) g(d) = \sum_{d \mid n} \mu(n/d) \sum_{e \mid d} f(e) = \sum_{e \mid n} f(e) \sum_{d: e \mid d \mid n} \mu(n/d) = \sum_{e \mid n} f(e) \cdot [\frac{n}{e} = 1] = f(n)$

using $\sum_{d \mid m} \mu(d) = [m = 1]$ . $\square$

Theorem 2 (Multidimensional Inversion)

If $g(n_1, \ldots, n_k) = \sum_{d_1 \mid n_1} \cdots \sum_{d_k \mid n_k} f(d_1, \ldots, d_k)$ , then:

f(n_1, \ldots, n_k) = \sum_{d_1 \mid n_1} \cdots \sum_{d_k \mid n_k} \mu(n_1/d_1) \cdots \mu(n_k/d_k) \cdot g(d_1, \ldots, d_k)

Theorem 3 (Inclusion-Exclusion Connection)

For squarefree arguments, Mobius inversion reduces to inclusion-exclusion:

\sum_{d \mid n} \mu(d) = [n = 1] = \sum_{S \subseteq P(n)} (-1)^{|S|}

where $P(n)$ is the set of prime factors of $n$ .

Theorem 4 (Sieve of Coprime Tuples)

The number of $k$ -tuples $(a_1, \ldots, a_k)$ with $1 \leq a_i \leq N$ and $\gcd(a_1, \ldots, a_k) = 1$ :

C_k(N) = \sum_{d=1}^{N} \mu(d) \lfloor N/d \rfloor^k

Proof. By Mobius inversion on $\sum_{d \mid \gcd(\mathbf{a})} \mu(d) = [\gcd(\mathbf{a}) = 1]$ :

C_k(N) = \sum_\mathbf{a} [\gcd = 1] = \sum_\mathbf{a} \sum_{d \mid \gcd} \mu(d) = \sum_d \mu(d) \lfloor N/d \rfloor^k \qquad \square

Concrete Numerical Examples

Mobius Function Values

$n$	$\mu(n)$	Reason
1	1	Empty product
2	$-1$	One prime factor
3	$-1$	One prime factor
4	0	$4 = 2^2$ , not squarefree
5	$-1$	Prime
6	1	$6 = 2 \times 3$ , two factors
12	0	$12 = 2^2 \times 3$
30	$-1$	$30 = 2 \times 3 \times 5$ , three factors

Coprime Pairs $C_2(N)$

$N$	$C_2(N) = \sum_d \mu(d) \lfloor N/d \rfloor^2$	Direct count
1	1	1
2	3	3
3	7	7
5	19	19
10	63	63

Euler Totient via Mobius

$\phi(n) = \sum_{d \mid n} \mu(d) \cdot (n/d) = n \prod_{p \mid n} (1 - 1/p)$

$n$	$\phi(n)$	$n \prod(1-1/p)$
6	2	$6 \cdot 1/2 \cdot 2/3 = 2$
12	4	$12 \cdot 1/2 \cdot 2/3 = 4$
30	8	$30 \cdot 1/2 \cdot 2/3 \cdot 4/5 = 8$

Dirichlet Convolution

The Mobius function is the Dirichlet inverse of the constant function $\mathbf{1}(n) = 1$ . For arithmetic functions $f, g$ :

(f * g)(n) = \sum_{d \mid n} f(d) g(n/d)

Key identities:

$\mu * \mathbf{1} = \varepsilon$ (identity for Dirichlet convolution)
$\phi = \mu * \text{id}$ (Euler’s totient)
$\sigma_k = \text{id}_k * \mathbf{1}$ (divisor power sum)

Mertens Function

$M(n) = \sum_{k=1}^{n} \mu(k)$ . The Mertens conjecture $|M(n)| < \sqrt{n}$ was disproven by Odlyzko and te Riele (1985), but $M(n) = O(\sqrt{n})$ is equivalent to the Riemann Hypothesis.

Complexity Analysis

Operation	Time
Sieve $\mu(n)$ up to $N$	$O(N \log \log N)$
$C_k(N)$ via Mobius sieve	$O(N)$
Multidimensional Mobius transform	$O(N^k \log N)$
Dirichlet convolution	$O(N \log N)$ or $O(N \sqrt{N})$

Answer

\boxed{227429102}

C++ project_euler/problem_888/solution.cpp

/*
 * Problem 888: Multidimensional Sieve
 * Mobius function sieve and coprime tuple counting.
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> mobius_sieve(int N) {
    vector<int> mu(N + 1, 0), primes;
    vector<bool> is_prime(N + 1, true);
    mu[1] = 1;
    for (int i = 2; i <= N; i++) {
        if (is_prime[i]) { primes.push_back(i); mu[i] = -1; }
        for (int p : primes) {
            if ((ll)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;
}

ll coprime_pairs(int N, const vector<int>& mu) {
    ll total = 0;
    for (int d = 1; d <= N; d++)
        total += (ll)mu[d] * (N / d) * (N / d);
    return total;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N = 1000;
    auto mu = mobius_sieve(N);

    cout << "=== Mobius Function ===" << endl;
    for (int n = 1; n <= 30; n++)
        cout << "mu(" << n << ") = " << mu[n] << endl;

    cout << "\n=== Coprime Pairs ===" << endl;
    for (int n : {10, 50, 100, 500, 1000})
        cout << "C_2(" << n << ") = " << coprime_pairs(n, mu) << endl;

    cout << "\nAnswer: C_2(1000) = " << coprime_pairs(1000, mu) << endl;
    return 0;
}

Python project_euler/problem_888/solution.py

"""
Problem 888: Multidimensional Sieve
Mobius inversion and inclusion-exclusion over prime factors.
"""

from math import gcd, isqrt

def mobius_sieve(N):
    """Compute mu(n) for n = 0..N."""
    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

def coprime_pairs(N, mu):
    """Count pairs (a,b) in [1,N]^2 with gcd(a,b) = 1."""
    total = 0
    for d in range(1, N + 1):
        total += mu[d] * (N // d) ** 2
    return total

def coprime_pairs_brute(N):
    """Brute force count."""
    count = 0
    for a in range(1, N + 1):
        for b in range(1, N + 1):
            if gcd(a, b) == 1:
                count += 1
    return count

def euler_totient_via_mobius(n, mu):
    """phi(n) = sum_{d|n} mu(d) * (n/d)."""
    total = 0
    for d in range(1, n + 1):
        if n % d == 0:
            total += mu[d] * (n // d)
    return total

# --- Verification ---
N = 100
mu = mobius_sieve(N)

print("=== Mobius Function ===")
for n in range(1, 31):
    print(f"  mu({n:>2}) = {mu[n]:>2}")

print("\n=== Coprime Pairs ===")
for N_test in [1, 2, 3, 5, 10, 20]:
    fast = coprime_pairs(N_test, mu)
    brute = coprime_pairs_brute(N_test)
    print(f"  C_2({N_test:>2}) = {fast:>5} (fast), {brute:>5} (brute), "
          f"{'OK' if fast == brute else 'FAIL'}")
    assert fast == brute

print("\n=== Euler Totient via Mobius ===")
for n in [1, 2, 3, 4, 6, 10, 12, 20, 30]:
    phi = euler_totient_via_mobius(n, mu)
    print(f"  phi({n:>2}) = {phi}")

print("\n=== Verification: sum mu(d) for d|n ===")
for n in [1, 2, 6, 12, 30]:
    s = sum(mu[d] for d in range(1, n + 1) if n % d == 0)
    print(f"  sum mu(d) for d|{n} = {s} (should be {'1' if n == 1 else '0'})")
    assert s == (1 if n == 1 else 0)

answer = coprime_pairs(100, mu)
print(f"\nAnswer: C_2(100) = {answer}")

# --- 4-Panel Visualization ---

Multidimensional Sieve

Problem Statement

Problem 888: Multidimensional Sieve

Mathematical Analysis

Theorem 1 (Mobius Inversion, 1D)

Theorem 2 (Multidimensional Inversion)

Theorem 3 (Inclusion-Exclusion Connection)

Theorem 4 (Sieve of Coprime Tuples)

Concrete Numerical Examples

Mobius Function Values

Coprime Pairs $C_2(N)$

Euler Totient via Mobius

Dirichlet Convolution

Mertens Function

Complexity Analysis

Answer

Code

Problem Statement

Problem 888: Multidimensional Sieve

Mathematical Analysis

Theorem 1 (Mobius Inversion, 1D)

Theorem 2 (Multidimensional Inversion)

Theorem 3 (Inclusion-Exclusion Connection)

Theorem 4 (Sieve of Coprime Tuples)

Concrete Numerical Examples

Mobius Function Values

Coprime Pairs C2(N)C_2(N)C2​(N)

Euler Totient via Mobius

Dirichlet Convolution

Mertens Function

Complexity Analysis

Answer

Code

Coprime Pairs $C_2(N)$