Problem 838: Not Coprime

Mathematical Foundation

Theorem 1 (Mobius Coprime Count). The number of ordered pairs $(a,b)$ with $1 \le a, b \le N$ and $\gcd(a,b) = 1$ is

Proof. We use the fundamental identity $[\gcd(a,b)=1] = \sum_{d \mid \gcd(a,b)} \mu(d)$, which follows from the Mobius inversion formula applied to the constant function $\mathbf{1}$ and its Dirichlet inverse $\mu$. Summing over all ordered pairs:

The exchange of summation is justified by absolute convergence (all sums are finite). The inner sums count multiples of $d$ in $\{1, \ldots, N\}$, each equaling $\lfloor N/d \rfloor$. $\square$

Lemma 1 (Ordered to Unordered). The number of unordered coprime pairs $(a, b)$ with $1 \le a \le b \le N$ is

Proof. Among the $\Phi(N)$ ordered coprime pairs, the only pair with $a = b$ and $\gcd(a,a) = 1$ is $(1,1)$. All other coprime pairs $(a,b)$ with $a \ne b$ appear twice (as $(a,b)$ and $(b,a)$). Hence the number of unordered pairs is $\frac{\Phi(N) - 1}{2} + 1 = \frac{\Phi(N) + 1}{2}$. $\square$

Theorem 2 (Non-Coprime Count). The number of unordered non-coprime pairs is

Proof. The total number of unordered pairs $(a,b)$ with $1 \le a \le b \le N$ is $\binom{N}{2} + N = \frac{N(N+1)}{2}$ (including pairs with $a = b$). Subtracting the coprime pairs: $C(N) = \frac{N(N+1)}{2} - C_{\mathrm{cop}}(N)$. $\square$

Theorem 3 (Hyperbola Method). The sum $\sum_{d=1}^{N} \mu(d) \lfloor N/d \rfloor^2$ can be evaluated in $O(\sqrt{N})$ arithmetic operations, given prefix sums of the Mobius function $M(x) = \sum_{k=1}^{x} \mu(k)$.

Proof. The function $d \mapsto q(d) = \lfloor N/d \rfloor$ takes at most $2\lfloor\sqrt{N}\rfloor$ distinct values. For each distinct value $q$, the set of $d$ with $\lfloor N/d \rfloor = q$ forms a contiguous interval $[d_1, d_2]$ where $d_2 = \lfloor N/q \rfloor$ and $d_1 = \lfloor N/(q+1) \rfloor + 1$. The contribution of this block is

Summing over all $O(\sqrt{N})$ blocks gives the result. $\square$

Lemma 2 (Asymptotic Density). As $N \to \infty$, $\Phi(N) \sim \frac{6N^2}{\pi^2}$, so the probability that two random integers are coprime is $6/\pi^2 \approx 0.6079$.

Proof. $\Phi(N)/N^2 = \sum_{d=1}^{N} \mu(d)/d^2 + O(1/N) \to \sum_{d=1}^{\infty} \mu(d)/d^2 = \prod_p (1 - 1/p^2) = 1/\zeta(2) = 6/\pi^2$, where the Euler product follows from the multiplicativity of $\mu$ and the product formula for $\zeta(2)$. $\square$

Editorial

Count pairs (a, b) with 1 <= a <= b <= N such that gcd(a, b) > 1. Key identity: Phi(N) = sum_{d=1}^{N} mu(d) * floor(N/d)^2 counts ordered coprime pairs, then C(N) = N(N+1)/2 - (Phi(N)+1)/2. We linear sieve for Mobius function. We then iterate over p in primes. Finally, prefix sums (Mertens function).

Pseudocode

Linear sieve for Mobius function
for p in primes
Prefix sums (Mertens function)
Block summation (hyperbola method)
Compute answer

Complexity Analysis

• Time: $O(N)$ for the linear sieve and prefix sums; $O(\sqrt{N})$ for the block summation. Total: $O(N)$.
• Space: $O(N)$ for storing $\mu$ and $M$.

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 838: Not Coprime
 *
 * Count pairs (a,b) with 1 <= a <= b <= N and gcd(a,b) > 1.
 *
 * Method: Mobius sieve + block summation.
 *   Phi(N) = sum_{d=1}^{N} mu(d) * floor(N/d)^2  (ordered coprime pairs)
 *   C(N) = N(N+1)/2 - (Phi(N)+1)/2
 *
 * Two methods implemented for cross-verification.
 */

const int MAXN = 10000001;

int mu[MAXN];
long long M[MAXN];  // Mertens function prefix sums
bool is_prime[MAXN];
vector<int> primes;

void sieve_mobius(int n) {
    fill(is_prime, 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 ((long long)i * p > n) break;
            is_prime[i * p] = false;
            if (i % p == 0) {
                mu[i * p] = 0;
                break;
            }
            mu[i * p] = -mu[i];
        }
    }
    // Compute Mertens function
    M[0] = 0;
    for (int i = 1; i <= n; i++) {
        M[i] = M[i - 1] + mu[i];
    }
}

// Method 1: Block summation using Mertens prefix sums
long long solve_block(int N) {
    long long phi_N = 0;
    int d = 1;
    while (d <= N) {
        long long q = N / d;
        int d2 = N / q;
        phi_N += q * q * (M[d2] - M[d - 1]);
        d = d2 + 1;
    }
    long long total = (long long)N * (N + 1) / 2;
    long long coprime = (phi_N + 1) / 2;
    return total - coprime;
}

// Method 2: Direct summation (slower, for verification)
long long solve_direct(int N) {
    long long phi_N = 0;
    for (int d = 1; d <= N; d++) {
        long long q = N / d;
        phi_N += (long long)mu[d] * q * q;
    }
    long long total = (long long)N * (N + 1) / 2;
    long long coprime = (phi_N + 1) / 2;
    return total - coprime;
}

int main() {
    int N = 10000000;
    sieve_mobius(N);

    long long ans1 = solve_block(N);
    long long ans2 = solve_direct(N);

    assert(ans1 == ans2);
    cout << ans1 << endl;
    return 0;
}

"""
Problem 838: Not Coprime

Count pairs (a, b) with 1 <= a <= b <= N such that gcd(a, b) > 1.

Key identity: Phi(N) = sum_{d=1}^{N} mu(d) * floor(N/d)^2
counts ordered coprime pairs, then C(N) = N(N+1)/2 - (Phi(N)+1)/2.
"""

from math import gcd

# --- Method 1: Direct Mobius sieve ---
def mobius_sieve(n: int) -> list:
    """Compute mu(k) for k = 0..n via linear sieve."""
    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 count_non_coprime_sieve(N: int):
    """Count non-coprime pairs using full Mobius sieve + block summation."""
    mu = mobius_sieve(N)
    # Prefix sums of mu (Mertens function)
    M = [0] * (N + 2)
    for i in range(1, N + 1):
        M[i] = M[i - 1] + mu[i]

    # Block summation: sum mu(d) * floor(N/d)^2
    phi_N = 0
    d = 1
    while d <= N:
        q = N // d
        # Find largest d2 with floor(N/d2) = q
        d2 = N // q
        phi_N += q * q * (M[d2] - M[d - 1])
        d = d2 + 1

    total_pairs = N * (N + 1) // 2
    coprime_pairs = (phi_N + 1) // 2
    return total_pairs - coprime_pairs

# --- Method 2: Brute force (for verification on small N) ---
def count_non_coprime_brute(N: int):
    """Brute force: enumerate all pairs and check gcd."""
    count = 0
    for a in range(1, N + 1):
        for b in range(a, N + 1):
            if gcd(a, b) > 1:
                count += 1
    return count

# --- Method 3: Euler totient summation ---
def count_non_coprime_totient(N: int):
    """Use Euler's totient: sum_{a=1}^{N} phi(a) = coprime pairs count (ordered, a<b) + N.
    Actually, sum_{a=1}^{N} phi(a) = (Phi(N) + 1) / 2 where Phi counts ordered coprime pairs.
    More precisely: number of (a,b) with 1<=b<=a<=N and gcd(a,b)=1 is sum phi(a).
    """
    # Compute phi via sieve
    phi = list(range(N + 1))
    for p in range(2, N + 1):
        if phi[p] == p:  # p is prime
            for m in range(p, N + 1, p):
                phi[m] -= phi[m] // p
    coprime_le = sum(phi[1:N + 1])  # sum phi(a) for a=1..N = coprime (b,a) with b<=a
    total_pairs = N * (N + 1) // 2
    return total_pairs - coprime_le

# --- Compute and verify ---
# Verify on small N
for n in range(1, 50):
    bf = count_non_coprime_brute(n)
    sv = count_non_coprime_sieve(n)
    tot = count_non_coprime_totient(n)
    assert bf == sv == tot, f"Mismatch at N={n}: brute={bf}, sieve={sv}, totient={tot}"

# Compute for target
N = 10_000_000
answer = count_non_coprime_sieve(N)
print(answer)