Problem 248: Numbers for which Euler’s Totient Function Equals 13!

Mathematical Foundation

Theorem 1 (Totient product formula). For $n = \prod_{i=1}^{k} p_i^{a_i}$ with distinct primes $p_i$,

Proof. This is standard: among the $p^a$ multiples of 1 up to $p^a$, exactly $p^{a-1}$ are divisible by $p$, so $\varphi(p^a) = p^a - p^{a-1} = p^{a-1}(p-1)$. Multiplicativity of $\varphi$ for coprime arguments completes the proof. $\square$

Lemma 1 (Candidate prime criterion). If $p^a \mid n$ with $p$ prime and $a \ge 1$, then $p^{a-1}(p-1) \mid \varphi(n) = 13!$. In particular, $(p-1) \mid 13!$.

Proof. From Theorem 1, $p^{a-1}(p-1)$ is one factor in the product for $\varphi(n)$, hence divides $\varphi(n) = 13!$. $\square$

Theorem 2 (Candidate prime enumeration). The set of primes $p$ that can divide any $n$ with $\varphi(n) = 13!$ is

Since $13! = 2^{10} \cdot 3^5 \cdot 5^2 \cdot 7 \cdot 11 \cdot 13$, the divisors of $13!$ that are one less than a prime determine $\mathcal{P}$. There are exactly 459 such primes.

Proof. By Lemma 1, any prime dividing $n$ must satisfy $(p-1) \mid 13!$. Conversely, for each divisor $d$ of $13!$, if $d + 1$ is prime, it is a candidate. Exhaustive enumeration of the $\tau(13!) = 11 \cdot 6 \cdot 3 \cdot 2 \cdot 2 \cdot 2 = 1584$ divisors of $13!$ and primality testing yields 459 primes. $\square$

Theorem 3 (Recursive construction). All solutions $n$ to $\varphi(n) = T$ (with $T = 13!$) can be enumerated by the following recursive procedure. Choose primes $p_1 \le p_2 \le \cdots$ from $\mathcal{P}$ and exponents $a_i \ge 1$, building $n = \prod p_i^{a_i}$ while maintaining the residual target $T' = T / \prod p_i^{a_i - 1}(p_i - 1)$. The recursion terminates when $T' = 1$ (valid solution) or $T' < 1$ (prune).

Proof. Every $n$ with $\varphi(n) = T$ has a unique prime factorisation. By processing primes in non-decreasing order, each factorisation is visited exactly once. The residual target tracks the remaining totient to be achieved, and each chosen prime-power $p^a$ contributes $p^{a-1}(p-1)$ to the totient. The recursion explores all valid combinations exhaustively. $\square$

Lemma 2 (Exponent bound). For prime $p$ with residual target $T'$, the maximum exponent $a$ satisfies $p^{a-1}(p-1) \le T'$, i.e., $a \le 1 + \lfloor \log_p(T'/(p-1)) \rfloor$.

Proof. The contribution $p^{a-1}(p-1)$ must divide $T'$, hence not exceed it. $\square$

Editorial

We find candidate primes. Finally, recursive enumeration. We perform a recursive search over the admissible choices, prune branches that violate the derived constraints, and keep only the candidates that satisfy the final condition.

Pseudocode

Find candidate primes
Recursive enumeration
Sort and return 150000th

Complexity Analysis

• Time: The recursion tree has branching factor bounded by $|\mathcal{P}| = 459$ at each level, but the residual target shrinks multiplicatively, limiting depth to $O(\log T / \log 2) \approx 33$. Empirically, about $548{,}000$ solutions are found, with search time dominated by the enumeration. Sorting: $O(N \log N)$ with $N \approx 548{,}000$.
• Space: $O(N)$ to store all solutions, plus $O(\log T)$ recursion stack depth.

Answer

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

int main() {
    // Find the 150000th number n for which phi(n) = 13!
    long long target = 6227020800LL; // 13!

    // Factorization of 13! = 2^10 * 3^5 * 5^2 * 7 * 11 * 13
    vector<pair<long long, int>> factors = {{2,10},{3,5},{5,2},{7,1},{11,1},{13,1}};

    // Generate all divisors
    vector<long long> divisors;
    divisors.push_back(1);
    for (auto& [p, e] : factors) {
        int sz = divisors.size();
        long long pk = 1;
        for (int k = 1; k <= e; k++) {
            pk *= p;
            for (int i = 0; i < sz; i++) {
                divisors.push_back(divisors[i] * pk);
            }
        }
    }
    sort(divisors.begin(), divisors.end());

    auto isPrime = [](long long n) -> bool {
        if (n < 2) return false;
        if (n < 4) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        for (long long i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) return false;
        }
        return true;
    };

    // Candidate primes
    vector<long long> primes;
    for (long long d : divisors) {
        if (isPrime(d + 1)) {
            primes.push_back(d + 1);
        }
    }
    sort(primes.begin(), primes.end());
    primes.erase(unique(primes.begin(), primes.end()), primes.end());

    // Recursively find all n such that phi(n) = target
    // n = p1^a1 * p2^a2 * ... where p1 < p2 < ...
    // phi(n) = prod(pi^(ai-1) * (pi-1))

    vector<long long> solutions;

    function<void(int, long long, long long)> search = [&](int idx, long long rem, long long n) {
        if (rem == 1) {
            // n and 2*n both have the same totient if n is odd
            // But p=2 with k=1 contributes factor 1 to phi, so 2*n is handled
            // when we include p=2 with k=1.
            solutions.push_back(n);
            return;
        }
        for (int i = idx; i < (int)primes.size(); i++) {
            long long p = primes[i];
            if (p - 1 > rem) break;
            if (rem % (p - 1) != 0) continue;
            long long r = rem / (p - 1);
            long long pk = 1; // p^(k-1), n_factor = p^k
            long long n_factor = p;
            while (true) {
                if (r % pk != 0) break;
                // Check overflow: n * n_factor
                if (n_factor > 1e18 / n) break; // overflow protection
                search(i + 1, r / pk, n * n_factor);
                pk *= p;
                n_factor *= p;
            }
        }
    };

    search(0, target, 1);

    sort(solutions.begin(), solutions.end());

    // 150000th (1-indexed)
    if ((int)solutions.size() >= 150000) {
        cout << solutions[150000 - 1] << endl;
    } else {
        cout << "Not enough solutions: " << solutions.size() << endl;
    }

    return 0;
}

import math

def solve():
    """
    Problem 248: Find the 150000th n with phi(n) = 13!
    """
    target = math.factorial(13)  # 6227020800

    # Factorization of 13! = 2^10 * 3^5 * 5^2 * 7 * 11 * 13
    factors = [(2, 10), (3, 5), (5, 2), (7, 1), (11, 1), (13, 1)]

    # Generate all divisors of 13!
    divisors = [1]
    for p, e in factors:
        new_divs = []
        for d in divisors:
            pk = 1
            for k in range(1, e + 1):
                pk *= p
                new_divs.append(d * pk)
        divisors.extend(new_divs)
    divisors.sort()

    def is_prime(n):
        if n < 2: return False
        if n < 4: return True
        if n % 2 == 0 or n % 3 == 0: return False
        i = 5
        while i * i <= n:
            if n % i == 0 or n % (i+2) == 0: return False
            i += 6
        return True

    # Candidate primes
    primes = sorted(set(d + 1 for d in divisors if is_prime(d + 1)))

    solutions = []

    def search(idx, rem, n):
        if rem == 1:
            solutions.append(n)
            return
        for i in range(idx, len(primes)):
            p = primes[i]
            if p - 1 > rem:
                break
            if rem % (p - 1) != 0:
                continue
            r = rem // (p - 1)
            pk = 1       # p^(k-1)
            n_factor = p # p^k
            while True:
                if r % pk != 0:
                    break
                if n_factor > 10**18 // max(n, 1):
                    break
                search(i + 1, r // pk, n * n_factor)
                pk *= p
                n_factor *= p

    search(0, target, 1)
    solutions.sort()
    print(solutions[150000 - 1])

solve()