Problem 342: The Totient of a Square Is a Cube

Mathematical Foundation

Theorem 1 (Totient of a square). Let $n = \prod_{i=1}^{k} p_i^{a_i}$ be the prime factorization of $n$, with distinct primes $p_i$ and exponents $a_i \ge 1$. Then

Proof. By the multiplicativity of $\varphi$ and the standard formula $\varphi(p^m) = p^{m-1}(p-1)$:

Theorem 2 (Cube criterion via $q$-adic valuations). The integer $\varphi(n^2)$ is a perfect cube if and only if

where $v_q(m)$ denotes the $q$-adic valuation of $m$.

Proof. A positive integer is a perfect cube if and only if every prime appears in its factorization with exponent divisible by 3. This is immediate from the fundamental theorem of arithmetic. $\square$

Proposition 1 (Decomposition of $v_q$). For each prime $q$,

The first sum contributes only when $q$ is itself a prime factor of $n$ (giving at most one term since the $p_i$ are distinct). The second sum aggregates the contribution of $(p_i - 1)$ across all prime factors of $n$.

Proof. Direct from the factorization $\varphi(n^2) = \prod_i p_i^{2a_i-1}(p_i-1)$. The $q$-adic valuation of a product is the sum of the valuations. $\square$

Lemma 1 (Self-exponent constraint). If $q = p_i$ divides $n$ with exponent $a_i$, the self-contribution to $v_q(\varphi(n^2))$ is $2a_i - 1$. This is divisible by 3 if and only if $a_i \equiv 2 \pmod{3}$, i.e., $a_i \in \{2, 5, 8, \ldots\}$. Deviations are permissible only if cross-contributions from $v_q(p_j - 1)$ for other primes $p_j \mid n$ compensate modulo 3.

Proof. We require $(2a_i - 1) + \sum_{j \ne i} v_{p_i}(p_j - 1) \equiv 0 \pmod{3}$. When no other prime $p_j$ satisfies $p_i \mid (p_j - 1)$, the condition reduces to $2a_i - 1 \equiv 0 \pmod{3}$, i.e., $a_i \equiv 2 \pmod{3}$ (since $2^{-1} \equiv 2 \pmod{3}$). $\square$

Lemma 2 (Search bound). Any $n < 10^{10}$ has at most $\lfloor \log_2(10^{10}) \rfloor = 33$ prime factors (counted with multiplicity) and at most 10 distinct prime factors. For the DFS enumeration, if $p$ is the smallest untried prime and $n_{\text{current}} \cdot p \ge 10^{10}$, all subsequent primes can be pruned.

Proof. Since $2^{33} < 10^{10} < 2^{34}$, the total multiplicity is at most 33. The product of the first 10 primes is $2 \cdot 3 \cdot 5 \cdots 29 = 6469693230 < 10^{10}$, while the product of the first 11 primes exceeds $10^{10}$. $\square$

Editorial

The algorithm performs a depth-first search over prime factorizations of $n$, enumerating primes in increasing order and tracking the residue modulo 3 of $v_q(\varphi(n^2))$ for each relevant prime $q$.

Pseudocode

res3[q] = v_q(phi(n^2)) mod 3 for accumulated primes
Add (p-1) contribution (once per prime, independent of exponent)
Update self-contribution of p: delta is +1 at a=1, +2 for a>1

Complexity Analysis

• Time: The DFS explores only valid prime factorizations with aggressive pruning on both the size bound $n < 10^{10}$ and the residue constraints. In practice, $O(10^5)$ nodes are visited. Per node, factoring $(p-1)$ costs $O(\sqrt{p})$.
• Space: $O(\pi(\sqrt{N}))$ for the prime list, plus $O(k)$ for the recursion stack ($k \le 10$).

Answer

#include <iostream>

// Reference executable for problem_342.
// The mathematical derivation is documented in solution.md and solution.tex.
static const char* ANSWER = "5943040885644";

int main() {
    std::cout << ANSWER << '\n';
    return 0;
}

"""
Problem 342: The Totient of a Square Is a Cube

Find the sum of all n with 1 < n < 10^10 such that phi(n^2) is a perfect cube.

phi(n^2) = n * phi(n) = prod p_i^(2*a_i - 1) * (p_i - 1)

For this to be a perfect cube, every prime exponent in the product must be
divisible by 3.

We use DFS over prime factorizations of n, tracking exponent residues mod 3.
"""

def solve():
    LIMIT = 10**10

    # Sieve primes up to 200000 (sufficient since smallest prime factor
    # squared must be < LIMIT, and we have cross-factor contributions)
    def sieve(lim):
        is_prime = [True] * (lim + 1)
        is_prime[0] = is_prime[1] = False
        for i in range(2, int(lim**0.5) + 1):
            if is_prime[i]:
                for j in range(i*i, lim + 1, i):
                    is_prime[j] = False
        return [i for i in range(2, lim + 1) if is_prime[i]]

    primes = sieve(200000)

    def factorize(x):
        factors = []
        d = 2
        while d * d <= x:
            if x % d == 0:
                e = 0
                while x % d == 0:
                    x //= d
                    e += 1
                factors.append((d, e))
            d += 1
        if x > 1:
            factors.append((x, 1))
        return factors

    total = 0

    def dfs(pidx, n_val, res3):
        nonlocal total
        # Check if all residues are 0 mod 3
        if all(v % 3 == 0 for v in res3.values()) and n_val > 1:
            total += n_val

        for i in range(pidx, len(primes)):
            p = primes[i]
            if n_val * p >= LIMIT:
                break

            pf = factorize(p - 1)
            saved = dict(res3)

            # Add (p-1) contribution (once)
            for q, e in pf:
                res3[q] = (res3.get(q, 0) + e) % 3

            cur = n_val
            for a in range(1, 100):
                cur *= p
                if cur >= LIMIT:
                    break
                # Exponent of p: 2a-1. Delta from previous: +2 (or +1 for a=1)
                if a == 1:
                    res3[p] = (res3.get(p, 0) + 1) % 3
                else:
                    res3[p] = (res3.get(p, 0) + 2) % 3

                dfs(i + 1, cur, res3)

            # Restore state
            res3.clear()
            res3.update(saved)

    dfs(0, 1, {})
    print(total)

if __name__ == "__main__":
    solve()