Project Euler

Sums of Totients of Powers

Let varphi denote Euler's totient function. Compute sum_(n=1)^N varphi(n^k) for given N and k. The specific instance asks for sum_(n=1)^(5 x 10^8) varphi(n) (i.e., k = 1).

Source sync Apr 19, 2026

Problem #0512

Level Level 11

Solved By 1,759

Languages C++, Python

Answer 50660591862310323

Length 259 words

number_theorydynamic_programmingrecursion

Let $\varphi (n)$ be Euler’s totient function.

Let $f(n)=(\displaystyle {\sum }_{i=1}^{n}\varphi (n^i)) \bmod (n+1)$.

Let $g(n)=\displaystyle {\sum }_{i=1}^{n} f(i)$.

You are given that $g(100)=2007$.

Find $g(5 \times 10^8)$.

Problem 512: Sums of Totients of Powers

Mathematical Foundation

Theorem 1 (Power Reduction). For all positive integers $n$ and $k \geq 1$ ,

\varphi(n^k) = n^{k-1}\,\varphi(n).

Proof. Let $n = \prod_{i} p_i^{a_i}$ be the prime factorization of $n$ . Then $n^k = \prod_i p_i^{k a_i}$ , so

\varphi(n^k) = \prod_i \varphi(p_i^{k a_i}) = \prod_i p_i^{k a_i - 1}(p_i - 1) = \prod_i p_i^{(k-1)a_i} \cdot \prod_i p_i^{a_i - 1}(p_i - 1) = n^{k-1}\,\varphi(n).

$\square$

Theorem 2 (Gauss Identity). For all positive integers $n$ ,

\sum_{d \mid n} \varphi(d) = n.

Proof. Partition $\{1, 2, \ldots, n\}$ by $\gcd(\cdot, n)$ : for each divisor $d \mid n$ , exactly $\varphi(n/d)$ integers in $\{1,\ldots,n\}$ satisfy $\gcd(m, n) = d$ . Summing over all divisors $d \mid n$ yields $\sum_{d \mid n} \varphi(n/d) = n$ . Since the sum over divisors is symmetric, $\sum_{d \mid n}\varphi(d) = n$ . $\square$

Lemma 1 (Summatory Totient Recursion). Define $\Phi(N) = \sum_{n=1}^{N}\varphi(n)$ . Then

\Phi(N) = \frac{N(N+1)}{2} - \sum_{d=2}^{N} \Phi\!\left(\left\lfloor \frac{N}{d} \right\rfloor\right).

Proof. Sum the Gauss identity over $n = 1, \ldots, N$ :

\sum_{n=1}^{N} n = \sum_{n=1}^{N}\sum_{d \mid n}\varphi(d) = \sum_{d=1}^{N}\sum_{\substack{n=1 \\ d \mid n}}^{N}\varphi(d) = \sum_{d=1}^{N}\varphi(d)\left\lfloor\frac{N}{d}\right\rfloor.

Wait — more carefully, exchanging the order of summation:

\frac{N(N+1)}{2} = \sum_{d=1}^{N} \sum_{m=1}^{\lfloor N/d \rfloor} \varphi(m) \cdot [\text{not quite}].

The correct derivation: from $\sum_{d \mid n}\varphi(d) = n$ , summing over $n \leq N$ :

\sum_{n=1}^{N} n = \sum_{n=1}^{N}\sum_{d \mid n}\varphi(d) = \sum_{d=1}^{N}\varphi(d)\left\lfloor\frac{N}{d}\right\rfloor.

This does not directly give the recursion for $\Phi$ . Instead, use the Dirichlet hyperbola approach:

\frac{N(N+1)}{2} = \sum_{d=1}^{N}\sum_{m=1}^{\lfloor N/d \rfloor}\varphi(m) = \sum_{d=1}^{N}\Phi\!\left(\left\lfloor\frac{N}{d}\right\rfloor\right).

Wait — that’s also not correct as stated. The standard derivation proceeds as follows. Define $f = \varphi * \mathbf{1}$ (Dirichlet convolution), so $f(n) = n$ by Gauss. Then $\sum_{n=1}^{N} f(n) = \sum_{n=1}^{N} \sum_{d \mid n}\varphi(d) = \sum_{d=1}^{N}\sum_{q=1}^{\lfloor N/d\rfloor}\varphi(q)$ . Thus:

\frac{N(N+1)}{2} = \sum_{d=1}^{N}\Phi\!\left(\left\lfloor\frac{N}{d}\right\rfloor\right).

Isolating the $d=1$ term: $\Phi(N) = \frac{N(N+1)}{2} - \sum_{d=2}^{N}\Phi\!\left(\left\lfloor\frac{N}{d}\right\rfloor\right)$ . $\square$

Theorem 3 (Sublinear Evaluation). Using the recursion in Lemma 1 with memoization and the fact that $\lfloor N/d \rfloor$ takes $O(\sqrt{N})$ distinct values, $\Phi(N)$ can be computed in $O(N^{2/3})$ time after pre-sieving $\varphi$ for $n \leq N^{2/3}$ .

Proof. The number of distinct values of $\lfloor N/d \rfloor$ for $1 \leq d \leq N$ is at most $2\lfloor\sqrt{N}\rfloor$ . Pre-sieving $\varphi(n)$ for $n \leq N^{2/3}$ costs $O(N^{2/3} \log\log N)$ time and provides all $\Phi(m)$ for $m \leq N^{2/3}$ by prefix summation. The remaining $O(N^{1/3})$ recursive calls each require $O(\sqrt{m})$ work to group the sum by distinct values of $\lfloor m/d \rfloor$ , giving total work $O(N^{2/3})$ . $\square$

Editorial

Compute sum of phi(n^k) for n = 1..N, using phi(n^k) = n^(k-1) * phi(n). Efficient totient sieve and sublinear summation. We pre-sieve phase.

Pseudocode

    Pre-sieve phase
    Set B <- floor(N^(2/3))
    Set phi[1..B] <- Euler_sieve(B) // O(B log log B)
    Set Phi_small[i] <- prefix_sum(phi, i) // for i = 1..B

    Set memo <- empty hash map

        if m <= B: return Phi_small[m]
        if m in memo: return memo[m]
        Set result <- m * (m + 1) / 2
        Set d <- 2
        While d <= m:
            Set q <- floor(m / d)
            Set d_max <- floor(m / q)
            result -= (d_max - d + 1) * Phi(q)
            Set d <- d_max + 1
        Set memo[m] <- result
        Return result

    Return Phi(N)

For the general $k$ case, compute $\sum_{n=1}^{N} n^{k-1}\varphi(n)$ using a sieve of $\varphi$ and direct summation.


## Complexity Analysis

- **Sieve approach (general $k$):** $O(N \log\log N)$ time, $O(N)$ space.
- **Sublinear method ($k = 1$):** $O(N^{2/3})$ time, $O(N^{2/3})$ space.

## Answer

$$
\boxed{50660591862310323}
$$

C++ project_euler/problem_512/solution.cpp

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

// Totient sieve: compute phi(n) for all n in [0, N]
vector<int> totient_sieve(int N) {
    vector<int> phi(N + 1);
    iota(phi.begin(), phi.end(), 0);  // phi[n] = n
    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 * (p - 1);
            }
        }
    }
    return phi;
}

// Sum of phi(n^k) = sum of n^(k-1) * phi(n) for n = 1..N
ll sum_totient_powers(int N, int k) {
    auto phi = totient_sieve(N);
    ll total = 0;
    for (int n = 1; n <= N; n++) {
        ll nk = 1;
        for (int j = 0; j < k - 1; j++) nk *= n;  // n^(k-1)
        total += nk * phi[n];
    }
    return total;
}

// Sublinear sum of phi(n) for n = 1..N
// O(N^{2/3}) using the hyperbola method
ll sum_totient_sublinear(ll N) {
    if (N <= 1) return N;

    int cbrt_N = (int)cbrt((double)N) + 1;
    int small = min((ll)cbrt_N * cbrt_N, N);
    // If N is too large for sieve, limit small
    if (small > 5000000) small = 5000000;
    small = min(small, (int)N);

    auto phi = totient_sieve(small);
    vector<ll> prefix(small + 1, 0);
    for (int i = 1; i <= small; i++) {
        prefix[i] = prefix[i-1] + phi[i];
    }

    unordered_map<ll, ll> memo;

    function<ll(ll)> Phi = [&](ll n) -> ll {
        if (n <= small) return prefix[n];
        auto it = memo.find(n);
        if (it != memo.end()) return it->second;

        ll result = n * (n + 1) / 2;
        ll d = 2;
        while (d <= n) {
            ll q = n / d;
            ll d_next = n / q + 1;
            result -= (d_next - d) * Phi(q);
            d = d_next;
        }

        memo[n] = result;
        return result;
    };

    return Phi(N);
}

int main() {
    // Compute sum of phi(n) for n = 1..N
    int N = 10000;
    auto phi = totient_sieve(N);

    // Display first 20
    cout << "First 20 totient values:" << endl;
    for (int n = 1; n <= 20; n++) {
        cout << "  phi(" << n << ") = " << phi[n] << endl;
    }

    // Sum phi(n)
    ll sum1 = 0;
    for (int n = 1; n <= N; n++) sum1 += phi[n];
    cout << "\nSum phi(n) for n=1.." << N << ": " << sum1 << endl;

    // Sum phi(n^2) = sum n*phi(n)
    ll sum2 = sum_totient_powers(N, 2);
    cout << "Sum phi(n^2) for n=1.." << N << ": " << sum2 << endl;

    // Sublinear
    ll N_large = 1000000;
    ll sub = sum_totient_sublinear(N_large);
    cout << "\nSum phi(n) for n=1.." << N_large << ": " << sub << endl;

    return 0;
}

Python project_euler/problem_512/solution.py

"""
Problem 512: Sums of Totients of Powers
Compute sum of phi(n^k) for n = 1..N, using phi(n^k) = n^(k-1) * phi(n).
Efficient totient sieve and sublinear summation.
"""

import numpy as np

def totient_sieve(N: int) -> list:
    """
    Compute phi(n) for all n from 0 to N using a sieve.
    O(N log log N) time, O(N) space.
    """
    phi = list(range(N + 1))  # phi[n] = n initially
    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 * (p - 1)
    return phi

def sum_totient_powers_sieve(N: int, k: int):
    """
    Compute sum of phi(n^k) for n = 1..N.
    Uses phi(n^k) = n^(k-1) * phi(n).
    """
    phi = totient_sieve(N)
    total = 0
    for n in range(1, N + 1):
        total += pow(n, k - 1) * phi[n]
    return total

def sum_totient_sublinear(N: int):
    """
    Compute sum of phi(n) for n = 1..N in O(N^{2/3}) time.
    Uses the identity: sum_{n=1}^{N} phi(n) = N*(N+1)/2 - sum_{d=2}^{N} Phi(floor(N/d))
    """
    if N <= 0:
        return 0

    # For small values, use sieve
    cbrt_N = int(N ** (2/3)) + 1
    small_limit = min(cbrt_N, N)
    phi_small = totient_sieve(small_limit)
    prefix = [0] * (small_limit + 1)
    for i in range(1, small_limit + 1):
        prefix[i] = prefix[i-1] + phi_small[i]

    memo = {}

    def Phi(n):
        if n <= small_limit:
            return prefix[n]
        if n in memo:
            return memo[n]

        result = n * (n + 1) // 2
        d = 2
        while d <= n:
            q = n // d
            d_next = n // q + 1
            result -= (d_next - d) * Phi(q)
            d = d_next

        memo[n] = result
        return result

    return Phi(N)

def brute_force_totient_sum(N: int):
    """Brute-force sum of phi(n) for verification."""
    phi = totient_sieve(N)
    return sum(phi[1:N+1])

# Verify sieve
N_test = 100
phi = totient_sieve(N_test)
print("First 20 totient values:")
for n in range(1, 21):
    print(f"  phi({n}) = {phi[n]}")

# Verify sum
sum_sieve = brute_force_totient_sum(N_test)
sum_sub = sum_totient_sublinear(N_test)
print(f"\nSum of phi(n) for n=1..{N_test}:")
print(f"  Sieve: {sum_sieve}")
print(f"  Sublinear: {sum_sub}")
print(f"  Match: {'YES' if sum_sieve == sum_sub else 'NO'}")

# Sum of phi(n^2) = sum of n * phi(n)
N_main = 10000
total_k1 = sum_totient_powers_sieve(N_main, 1)
total_k2 = sum_totient_powers_sieve(N_main, 2)
total_k3 = sum_totient_powers_sieve(N_main, 3)
print(f"\nFor N = {N_main}:")
print(f"  Sum phi(n)   = {total_k1}")
print(f"  Sum phi(n^2) = {total_k2}")
print(f"  Sum phi(n^3) = {total_k3}")

# Sublinear for larger N
N_large = 10**6
large_sum = sum_totient_sublinear(N_large)
print(f"\nSum phi(n) for n=1..{N_large}: {large_sum}")

# Known: sum phi(n) for n=1..N ~ 3N^2/pi^2
approx = 3 * N_large**2 / (np.pi**2)
print(f"  Approximation 3N^2/pi^2 = {approx:.0f}")
print(f"  Ratio: {large_sum / approx:.6f}")

Sums of Totients of Powers

Problem Statement

Problem 512: Sums of Totients of Powers

Mathematical Foundation

Editorial

Pseudocode

Code