Detailed mathematical approach

Problem Summary

For a positive integer \(n\), Euler's totient \(\varphi(n)\) counts how many integers from \(1\) to \(n\) are coprime to \(n\). The task is to find the value of \(n \le 1{,}000{,}000\) that maximizes the ratio \(n/\varphi(n)\).

A brute-force scan over all integers is unnecessary. The decisive observation is that the ratio can be rewritten entirely in terms of the distinct prime divisors of \(n\), and that turns the search into a short product of consecutive primes.

Mathematical Approach

The full derivation comes from Euler's product formula for the totient function and from a simple exchange argument on prime factors.

The ratio depends only on distinct prime divisors

If

$n=\prod_{i=1}^{k} p_i^{a_i},$

then the totient function satisfies

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

Therefore

$\frac{n}{\varphi(n)}=\prod_{p\mid n}\frac{1}{1-\frac{1}{p}}=\prod_{p\mid n}\frac{p}{p-1}.$

This identity is the key invariant of the problem. The exponents \(a_i\) disappear completely, so the ratio depends only on which primes divide \(n\), not on how many times they divide it. For example, \(6=2\cdot 3\) and \(12=2^2\cdot 3\) both have ratio \(3\).

Why extra powers of a prime never help

Because the ratio ignores multiplicities, increasing the exponent of an existing prime makes \(n\) larger without improving \(n/\varphi(n)\). That means an optimal value can always be chosen squarefree:

$n=p_1p_2\cdots p_k.$

Under the constraint \(n \le L\), spending part of the size budget on \(p^2,p^3,\dots\) is wasteful. It is always better to reserve that budget for introducing a new prime divisor, because a new prime contributes a fresh factor \(p/(p-1)\) greater than 1.

Why the optimal prime set must start with 2, 3, 5, ...

For primes \(p<q\), we have

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

So smaller primes improve the ratio more than larger primes do. Suppose a squarefree candidate contains \(q\) but omits a smaller prime \(p\). Replace \(q\) by \(p\) and define

$m=n\frac{p}{q}.$

Then \(m<n\), while

$\frac{m}{\varphi(m)}=\frac{n}{\varphi(n)}\cdot \frac{p/(p-1)}{q/(q-1)} > \frac{n}{\varphi(n)}.$

So any maximizer that uses a larger prime must also use every smaller prime. The prime divisors of the optimum therefore form an initial segment of the primes:

$2,3,5,7,\dots,p_k.$

The product of the first \(k\) primes is called a primorial, so the answer is the largest primorial that does not exceed the limit.

Worked example at the bound \(10^6\)

Start from 1 and multiply consecutive primes:

$2,\quad 2\cdot 3=6,\quad 6\cdot 5=30,\quad 30\cdot 7=210,\quad 210\cdot 11=2310,$

$2310\cdot 13=30030,\qquad 30030\cdot 17=510510,\qquad 510510\cdot 19=9699690.$

The product through \(17\) is still below \(1{,}000{,}000\), but multiplying by \(19\) overshoots the bound. Therefore

$\boxed{510510=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17}$

is the maximizing value.

A smaller comparison shows why the proof works. Moving from \(6\) to \(12\) only increases the exponent of \(2\), so the ratio stays at \(3\). Moving from \(6\) to \(30\) introduces the new prime \(5\), so the ratio is multiplied by \(5/4\) and rises to \(15/4\).

How the Code Works

The C++, Python, and Java implementations follow the proof directly instead of computing totients for every integer up to the limit. They first generate a short list of primes with a sieve. For the Project Euler bound, sieving up to \(100\) is more than enough, because the relevant prime chain stops at \(19\).

They then keep a running product and multiply by primes in increasing order. As soon as the next multiplication would exceed the chosen limit, the loop stops, and the current product is returned. At every stage that product is exactly the largest primorial still allowed by the bound.

The implementations also support a configurable limit and include a small checkpoint: when the limit is \(10\), the best value is \(6\). No totient table, divisor scan, or search over all candidates is needed, because the mathematics has already reduced the problem to a handful of prime multiplications.

Complexity Analysis

Within this implementation, prime generation is done only up to \(100\), so the sieve cost is effectively constant, both in time and in memory. After that, the multiplication loop touches only the first few primes and stops once the next prime would cross the limit.

For the specific bound \(1{,}000{,}000\), the loop only needs the primes \(2,3,5,7,11,13,17,19\), so the overall computation is tiny. In practical terms, both runtime and memory usage are constant for this problem.

Footnotes and References

1. Problem page: Project Euler 69
2. Euler's totient function: Wikipedia - Euler's totient function
3. Primorials: Wikipedia - Primorial
4. Coprime integers: Wikipedia - Coprime integers