Solution

Answer: 8319823

We seek the integer $n < 10^7$ such that:

$\phi(n)$ is a permutation of $n$, and
the ratio

$$\frac{n}{\phi(n)}$$

is minimized.

Mathematical Analysis

1. Euler's Totient Function

Euler’s totient function counts integers relatively prime to $n$.

$$n = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k},$$

then

$$\phi(n)=n\prod_{p\mid n}\left(1-\frac1p\right).$$

Equivalently,

$$\frac{n}{\phi(n)} = \prod_{p\mid n}\frac1{1-\frac1p} = \prod_{p\mid n}\frac{p}{p-1}.$$

This formula is the key insight.

2. How to Minimize $n/\phi(n)$

Notice:

Every distinct prime factor contributes a multiplicative factor

$$\frac{p}{p-1}>1.$$

Small primes increase the ratio more strongly:

$$\frac{2}{1}=2,\qquad \frac{3}{2}=1.5,\qquad \frac{5}{4}=1.25,\dots$$

Thus:

To make $n/\phi(n)$ small, we want:
as few distinct prime factors as possible,
and preferably large primes.

So the best candidates are numbers of the form

$$n=pq$$

with two large primes near $\sqrt{10^7}$.

Why not a prime?

If $n=p$, then

$$\phi(p)=p-1,$$

which cannot be a digit permutation of $p$.

Why not prime powers?

For $n=p^k$,

$$\phi(n)=p^{k-1}(p-1),$$

and digit permutations become extremely unlikely.

Hence semiprimes $pq$ are the natural candidates.

3. Formula for Semiprimes

$$n=pq$$

with distinct primes $p,q$, then

$$\phi(n)=(p-1)(q-1)=pq-p-q+1.$$

The ratio becomes

$$\frac{n}{\phi(n)} = \frac{pq}{(p-1)(q-1)}.$$

To minimize this:

choose large primes,
close together,
while ensuring the permutation condition.

4. Search Strategy

We need all primes up to roughly:

$$\sqrt{10^7}\approx3162.$$

Then:

Generate primes up to 10,000 (safe bound).
Iterate over pairs $p<q$.
Compute:

$$n=pq,\qquad \phi=(p-1)(q-1).$$ 4. Check:

$n<10^7$,
sorted digits of $n$ equal sorted digits of $\phi$.

Track the minimum ratio.

This is efficient because the prime count is small.

Python Implementation

from math import isqrt

LIMIT = 10_000_000

# -------------------------------------------------------
# Sieve of Eratosthenes
# -------------------------------------------------------
def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False

    for p in range(2, isqrt(n) + 1):
        if is_prime[p]:
            step = p
            start = p * p
            for multiple in range(start, n + 1, step):
                is_prime[multiple] = False

    return [i for i, prime in enumerate(is_prime) if prime]

# -------------------------------------------------------
# Check whether two numbers are digit permutations
# -------------------------------------------------------
def is_permutation(a, b):
    return sorted(str(a)) == sorted(str(b))

# Generate enough primes
primes = sieve(10000)

best_n = None
best_ratio = float('inf')

# -------------------------------------------------------
# Search semiprimes n = p*q
# -------------------------------------------------------
for i in range(len(primes)):
    p = primes[i]

    for j in range(i + 1, len(primes)):
        q = primes[j]

        n = p * q

        if n >= LIMIT:
            break

        phi = (p - 1) * (q - 1)

        # Check permutation condition
        if is_permutation(n, phi):

            ratio = n / phi

            if ratio < best_ratio:
                best_ratio = ratio
                best_n = n

print(best_n)

Code Walkthrough

Sieve

def sieve(n):

Implements the Sieve of Eratosthenes.

We mark multiples of each prime as composite.

The result is a list of all primes up to 10,000.

Permutation Test

def is_permutation(a, b):
    return sorted(str(a)) == sorted(str(b))

Two numbers are permutations iff their sorted digit lists match.

Example:

87109 -> ['0','1','7','8','9']
79180 -> ['0','1','7','8','9']

So they are permutations.

Main Search

We iterate over prime pairs:

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

If $n\ge10^7$, we stop increasing $q$.

For valid permutations:

ratio = n / phi

we keep the minimum.

Small Example Verification

The problem gives:

$$n=87109$$

and

$$\phi(87109)=79180.$$

Indeed:

Digits match.
Ratio:

$$\frac{87109}{79180}\approx1.1004.$$

Our program finds an even smaller ratio.

Final Verification

The optimal value found is:

$$n=8319823.$$

Factorization:

$$8319823 = 2339 \times 3557.$$

Then

$$\phi(n)=(2339-1)(3557-1)=8313928.$$

The digits are permutations:

$8319823$
$8313928$

and the ratio is

$$\frac{8319823}{8313928}\approx1.000709,$$

extremely close to 1, which is exactly what we expect from two large primes.

Therefore the result is consistent.

Answer: 8319823

Project Euler Problem 70