Problem 927: Totient Sum Optimization

Mathematical Foundation

Theorem 1 (Euler’s Product Formula). For $n = p_1^{a_1} \cdots p_r^{a_r}$:

Proof. By inclusion-exclusion on the set $\{1, \ldots, n\}$, subtracting multiples of each prime $p_i$ dividing $n$:

Alternatively, since $\varphi$ is multiplicative and $\varphi(p^a) = p^{a-1}(p-1)$ (there are $p^a - p^{a-1}$ integers in $\{1,\ldots,p^a\}$ coprime to $p$), the product formula follows from multiplicativity. $\square$

Theorem 2 (Divisor Sum Identity). For all $n \geq 1$: $\displaystyle\sum_{d \mid n} \varphi(d) = n$.

Proof. Partition $\{1, 2, \ldots, n\}$ by the value of $\gcd(k, n)$. For each divisor $d \mid n$, the set $\{k \in \{1,\ldots,n\} : \gcd(k,n) = d\}$ has cardinality $\varphi(n/d)$ (since $\gcd(k,n) = d$ iff $\gcd(k/d, n/d) = 1$, and $k/d$ ranges over $\{1,\ldots,n/d\}$). Summing: $\sum_{d \mid n} \varphi(n/d) = n$. Reindexing $d' = n/d$ gives $\sum_{d' \mid n} \varphi(d') = n$. $\square$

Theorem 3 (Sub-linear Recursion for $\Phi(N)$). Let $\Phi(N) = \sum_{k=1}^{N} \varphi(k)$. Then:

Proof. From Theorem 2, summing over $n = 1, \ldots, N$:

The left side is $N(N+1)/2$. Grouping by $m = \lfloor N/d \rfloor$:

Equivalently, using hyperbola-method notation: $\sum_{d=1}^{N} \varphi(d) \lfloor N/d \rfloor = \sum_{m=1}^{N} \Phi(\lfloor N/m \rfloor)$ (by Dirichlet’s hyperbola method applied to $\varphi * \mathbf{1} = \mathrm{id}$). Isolating $m = 1$:

Lemma 1 (Complexity of the Recursion). Using memoization and grouping identical values of $\lfloor N/k \rfloor$, the recursion computes $\Phi(N)$ in $O(N^{2/3})$ time and $O(N^{2/3})$ space.

Proof. The set $\{\lfloor N/k \rfloor : 1 \leq k \leq N\}$ has $O(\sqrt{N})$ distinct values. With a sieve precomputing $\Phi(m)$ for $m \leq N^{2/3}$, the remaining $O(N^{1/3})$ values are handled by the recursion, each requiring $O(\sqrt{m})$ work. Total: $O(N^{2/3})$. $\square$

Theorem 4 (Asymptotic Formula). $\Phi(N) = \frac{3N^2}{\pi^2} + O(N \log N)$.

Proof. Since $\varphi = \mu * \mathrm{id}$ (Mobius inversion of Theorem 2), the Dirichlet series $\sum \varphi(n)/n^s = \zeta(s-1)/\zeta(s)$. By standard Tauberian arguments (or Perron’s formula), $\Phi(N) = \frac{N^2}{2\zeta(2)} + O(N \log N) = \frac{3N^2}{\pi^2} + O(N \log N)$, using $\zeta(2) = \pi^2/6$. $\square$

Editorial

Compute the sum of Euler’s totient function phi(k) for k = 1..N, modulo 10^9+7. Uses a sieve-based approach to compute all phi values efficiently. Key ideas:.

Pseudocode

    Sieve phi(n) for n = 1..N, then sum
    phi[1..N]
    For n from 1 to N:
        phi[n] = n

    For p from 2 to N:
        if phi[p] == p: // p is prime
            For m from p to N step p:
                phi[m] = phi[m] / p * (p - 1)

    S = 0
    For n from 1 to N:
        S = (S + phi[n]) mod MOD

    Return S

Complexity Analysis

• Time: $O(N \log \log N)$ for the Euler sieve. The inner loop over primes $p$ processes $\lfloor N/p \rfloor$ multiples, and $\sum_{p \leq N} N/p = O(N \log \log N)$ by Mertens’ theorem.
• Space: $O(N)$ for the array $\varphi[1..N]$.

For the sub-linear approach: $O(N^{2/3})$ time and space (see Lemma 1).

Answer

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

/*
 * Problem 927: Totient Sum Optimization
 *
 * Find sum_{k=1}^{10^7} phi(k) mod 10^9+7.
 *
 * Euler sieve: phi(n) = n * prod_{p|n} (1 - 1/p).
 * Initialize phi[n] = n, then for each prime p:
 *   phi[m] -= phi[m]/p for all m divisible by p.
 *
 * Key identity: sum_{d|n} phi(d) = n.
 * Asymptotic: Phi(N) = 3N^2/pi^2 + O(N log N).
 *
 * Complexity: O(N log log N) sieve, O(N) summation.
 */

int main() {
    const int N = 10000000;
    const long long MOD = 1000000007;
    vector<int> phi(N + 1);
    iota(phi.begin(), phi.end(), 0);
    for (int p = 2; p <= N; p++) {
        if (phi[p] == p) { // p is prime
            for (int m = p; m <= N; m += p) {
                phi[m] -= phi[m] / p;
            }
        }
    }
    long long ans = 0;
    for (int k = 1; k <= N; k++) {
        ans = (ans + phi[k]) % MOD;
    }
    cout << ans << endl;

    // Verify: phi(1)=1, phi(2)=1, phi(6)=2, phi(12)=4
    assert(phi[1] == 1);
    assert(phi[2] == 1);
    assert(phi[6] == 2);
    assert(phi[12] == 4);

    return 0;
}

"""
Problem 927: Totient Sum Optimization

Compute the sum of Euler's totient function phi(k) for k = 1..N, modulo 10^9+7.
Uses a sieve-based approach to compute all phi values efficiently.

Key ideas:
    - phi(n) = n * product(1 - 1/p) for each prime p dividing n.
    - Sieve of Eratosthenes variant computes phi for all n in O(N log log N).
    - Summatory totient: Phi(N) = sum_{k=1}^{N} phi(k) ~ 3N^2 / pi^2.
    - phi(n)/n ratio distribution reflects multiplicative structure.

Methods:
    1. Euler sieve for phi(1..N)
    2. Direct phi computation via factorization (verification)
    3. Ratio phi(n)/n distribution analysis
    4. Summatory function vs asymptotic approximation
"""

from math import gcd

def euler_sieve(N):
    """Compute phi(0..N) using multiplicative 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
    return phi

def solve(N=10**7):
    MOD = 10**9 + 7
    phi = euler_sieve(N)
    return sum(phi[1:]) % MOD

def phi_direct(n):
    """Compute phi(n) by counting coprime integers."""
    if n <= 1:
        return n
    return sum(1 for k in range(1, n + 1) if gcd(k, n) == 1)

def phi_factor(n):
    """Compute phi(n) from prime factorization."""
    result = n
    p = 2
    temp = n
    while p * p <= temp:
        if temp % p == 0:
            while temp % p == 0:
                temp //= p
            result -= result // p
        p += 1
    if temp > 1:
        result -= result // temp
    return result

def summatory_totient(phi_list):
    """Compute cumulative sum of phi values."""
    cumsum = [0]
    for k in range(1, len(phi_list)):
        cumsum.append(cumsum[-1] + phi_list[k])
    return cumsum

# Solve and verify
answer = solve()

# Verify sieve against direct computation for small values
phi_small = euler_sieve(100)
for n in range(1, 101):
    assert phi_small[n] == phi_direct(n), f"Mismatch at n={n}"
    assert phi_small[n] == phi_factor(n), f"Factor mismatch at n={n}"

# Known values
assert phi_small[1] == 1
assert phi_small[2] == 1
assert phi_small[6] == 2
assert phi_small[12] == 4
assert phi_small[97] == 96  # prime

print(answer)