Solution

Answer: 510510

We want to maximize

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

for $n \le 1{,}000{,}000$, where $\phi(n)$ is Euler’s totient function.

Mathematical analysis

Euler’s totient function satisfies the fundamental formula

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

where the product is over the distinct prime divisors of $n$.

Therefore,

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

So the ratio depends only on the distinct primes dividing $n$.

Key insight

Each factor

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

is greater than $1$, so adding more distinct prime factors increases the ratio.

Also, smaller primes increase the ratio more efficiently:

$$\frac{2}{1}=2,\quad \frac{3}{2}=1.5,\quad \frac{5}{4}=1.25,\quad \frac{7}{6}\approx1.166\ldots$$

Thus, to maximize $n/\phi(n)$, we should multiply together the smallest distinct primes.

The optimal $n$ is therefore the largest product of consecutive small primes that does not exceed $1{,}000{,}000$.

Compute:

$$2=2$$

$$2\cdot3=6$$

$$2\cdot3\cdot5=30$$

$$2\cdot3\cdot5\cdot7=210$$

$$2\cdot3\cdot5\cdot7\cdot11=2310$$

$$2\cdot3\cdot5\cdot7\cdot11\cdot13=30030$$

$$2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17=510510$$

$$510510\cdot19=9699690>1{,}000{,}000$$

So the maximizing value is

$$n=510510$$

Python implementation

from math import prod

# Generate primes manually (small list is enough here)
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

limit = 1_000_000
n = 1

# Multiply consecutive primes while staying within the limit
for p in primes:
    if n * p > limit:
        break
    n *= p

print(n)

Code walkthrough

from math import prod

Imports Python’s math utilities (though prod is not strictly necessary here).

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

We only need a short list of small primes because the product grows quickly.

limit = 1_000_000
n = 1

Initialize the upper bound and the running product.

for p in primes:

Loop through primes in increasing order.

    if n * p > limit:
        break

If multiplying by the next prime exceeds the limit, stop.

    n *= p

Otherwise include that prime factor.

print(n)

Outputs the maximizing value.

The computation proceeds as:

$$1 \to 2 \to 6 \to 30 \to 210 \to 2310 \to 30030 \to 510510$$

The next multiplication by $19$ exceeds one million.

Small-example verification

For $n \le 10$:

$n=6$
$\phi(6)=2$
$6/2=3$

This matches the example in the problem statement.

Also,

$$\frac{510510}{\phi(510510)} = \prod_{p\in{2,3,5,7,11,13,17}}\frac{p}{p-1}$$

which is larger than for any number missing one of these small primes.

Final verification

$510510 < 1{,}000{,}000$
Multiplying by the next prime $19$ gives $9{,}699{,}690$, too large.
Using repeated prime powers would increase $n$ without changing the ratio, so distinct small primes are optimal.

Therefore the result is correct.

Answer: 510510

Project Euler Problem 69