Problem 70: Totient Permutation

Mathematical Analysis

Theorem 1 (Ratio Formula)

For $n = p_1^{a_1} \cdots p_k^{a_k}$:

Proof. Follows directly from $\varphi(n) = n \prod_{p \mid n}(1 - 1/p)$. $\square$

Theorem 2 (Minimization Principles)

To minimize $n/\varphi(n)$ subject to the permutation constraint:

1. Use as few distinct prime factors as possible (each factor $p/(p-1) > 1$ increases the ratio).
2. Use primes as large as possible ($p/(p-1) \to 1$ as $p \to \infty$).

Proof. Statement (1): If $n$ has $k$ distinct prime factors, then $n/\varphi(n) = \prod_{i=1}^k p_i/(p_i - 1) \geq (2/1)^k$ in the worst case, and is always $> 1$ for $k \geq 1$. Fewer factors yield a smaller product.

Statement (2): Among ratios with the same number of prime factors, $\prod p_i/(p_i-1)$ is minimized by choosing the largest possible primes (since $p/(p-1)$ is strictly decreasing). $\square$

Theorem 3 (Exclusion of Primes)

If $n = p$ is prime, then $\varphi(p) = p - 1$ is never a digit permutation of $p$.

Proof. Two integers are digit permutations of each other only if they are congruent modulo 9 (since the digit sum is invariant under permutation, and a number is congruent to its digit sum mod 9). However, $p - (p-1) = 1$, so $p \equiv p - 1 + 1 \pmod{9}$, meaning $p \not\equiv p - 1 \pmod{9}$ (as $1 \not\equiv 0 \pmod{9}$). Therefore $p$ and $p - 1$ cannot be digit permutations. $\square$

Corollary (Semiprimes Are Optimal Candidates)

Since primes are excluded by Theorem 3, the candidates with the fewest prime factors are semiprimes $n = pq$ (with $p, q$ distinct primes or $n = p^2$). For semiprimes:

This ratio is minimized when $p$ and $q$ are large and close to $\sqrt{10^7} \approx 3162$.

Proof. For fixed product $pq$, the ratio $pq/((p-1)(q-1))$ is minimized when $p$ and $q$ are as close as possible (by AM-GM, the denominator $(p-1)(q-1)$ is maximized for $p \approx q$). Furthermore, larger primes yield a ratio closer to 1. $\square$

Remark on $n = p^2$

For $n = p^2$, we have $\varphi(p^2) = p(p-1)$ and $n/\varphi(n) = p/(p-1)$, which has only one prime factor contributing. However, the permutation constraint $p^2 \leftrightarrow p(p-1)$ is hard to satisfy for large $p$, and in practice the semiprime form $n = pq$ with $p \neq q$ yields the optimum.

Search Strategy

Proposition. It suffices to search over pairs $(p, q)$ of primes with $p \leq q$ and $pq < 10^7$. For each pair, check whether $(p-1)(q-1)$ is a digit permutation of $pq$, and track the pair minimizing $pq/((p-1)(q-1))$.

Proof of sufficiency. By Theorem 3, $n$ cannot be prime. If $n$ has three or more distinct prime factors, then $n/\varphi(n) \geq (2/1)(3/2)(5/4) = 15/4 = 3.75$, whereas the semiprime candidate yields a ratio near 1. Products of prime powers with three or more factors are similarly dominated. Hence we need only search semiprimes. $\square$

Digit Permutation Criterion

Lemma. Two positive integers $a$ and $b$ are digit permutations of each other if and only if they have the same multiset of decimal digits, equivalently, the same sorted digit string.

Proof. By definition. $\square$

Editorial

The search is restricted to semiprimes $n = pq$, because the ratio $n/\varphi(n)$ is minimized there among non-prime candidates, especially when $p$ and $q$ are large and close to $\sqrt{10^7}$. We enumerate prime pairs $(p,q)$ with $p \le q$ and $pq < 10^7$, compute $\varphi(pq) = (p-1)(q-1)$, and test whether $\varphi(pq)$ is a digit permutation of $pq$. Among all pairs passing that test, we keep the one with the smallest ratio $n/\varphi(n)$.

Pseudocode

Generate the primes below the search bound.
Begin with no candidate and with the best ratio larger than every feasible value.

For each prime p whose square is still below 10^7:
    pair p with primes q starting from p itself
    stop the inner scan once pq reaches the bound

    for each admissible product n = pq:
        compute phi(n) = (p - 1)(q - 1)
        compare the decimal digit multisets of n and phi(n)

        if they are permutations of one another and the ratio n / phi(n) improves the current best:
            record this n as the new best candidate

Return the recorded best candidate.

Complexity

• Sieve: $O(N \log \log N)$ where $N = 10^7$.
• Search: $O(\pi(\sqrt{N})^2)$ pairs. By the Prime Number Theorem, $\pi(\sqrt{N}) \approx \sqrt{N}/\ln\sqrt{N}$, so this is $O(N/\log^2 N)$.
• Space: $O(N)$ for the prime sieve.

Answer

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

bool is_permutation(int a, int b) {
    int digits_a[10] = {}, digits_b[10] = {};
    while (a > 0) { digits_a[a % 10]++; a /= 10; }
    while (b > 0) { digits_b[b % 10]++; b /= 10; }
    for (int i = 0; i < 10; i++)
        if (digits_a[i] != digits_b[i]) return false;
    return true;
}

int main() {
    const int LIMIT = 10000000;

    // Sieve of Eratosthenes
    vector<bool> is_prime(LIMIT, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; (long long)i * i < LIMIT; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j < LIMIT; j += i)
                is_prime[j] = false;
        }
    }

    vector<int> primes;
    for (int i = 2; i < LIMIT; i++) {
        if (is_prime[i]) primes.push_back(i);
    }

    double best_ratio = 1e18;
    int best_n = 0;

    // Search semiprimes n = p * q with p <= q, pq < LIMIT
    for (int i = 0; i < (int)primes.size(); i++) {
        int p = primes[i];
        if ((long long)p * p >= LIMIT) break;
        for (int j = i; j < (int)primes.size(); j++) {
            int q = primes[j];
            long long n = (long long)p * q;
            if (n >= LIMIT) break;

            long long phi = (long long)(p - 1) * (q - 1);
            double ratio = (double)n / phi;

            if (ratio < best_ratio && is_permutation((int)n, (int)phi)) {
                best_ratio = ratio;
                best_n = (int)n;
            }
        }
    }

    cout << best_n << endl;

    return 0;
}

"""
Project Euler Problem 70: Totient Permutation

Find n, 1 < n < 10^7, for which phi(n) is a digit permutation of n
and n/phi(n) is minimized.

By Theorem 3, primes are excluded. By the Corollary, semiprimes n = p*q
with p, q near sqrt(10^7) are optimal candidates.
"""


def sieve_primes(limit):
    """Sieve of Eratosthenes returning list of primes up to limit."""
    is_prime = bytearray(b'\x01') * (limit + 1)
    is_prime[0] = is_prime[1] = 0
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            is_prime[i*i::i] = bytearray(len(is_prime[i*i::i]))
    return [i for i in range(2, limit + 1) if is_prime[i]]


def is_permutation(a, b):
    """Check if a and b have the same multiset of decimal digits."""
    return sorted(str(a)) == sorted(str(b))


def main():
    LIMIT = 10_000_000
    primes = sieve_primes(LIMIT)

    best_ratio = float('inf')
    best_n = 0

    for i in range(len(primes)):
        p = primes[i]
        if p * p >= LIMIT:
            break
        for j in range(i, len(primes)):
            q = primes[j]
            n = p * q
            if n >= LIMIT:
                break

            phi = (p - 1) * (q - 1)
            ratio = n / phi

            if ratio < best_ratio and is_permutation(n, phi):
                best_ratio = ratio
                best_n = n

    print(best_n)


if __name__ == "__main__":
    main()