Totient Maximum¶
This problem can be solved by hand.
The totient function can be computed as $$\phi(n) = n\prod_{p|n} \left(1 - \frac{1}{p}\right)$$ Therefore $$\frac{n}{\phi(n)} = \prod_{p|n}\left(\frac{p}{p-1}\right)$$ This implies that $n/\phi(n)$ increases as the number of distinct prime factors of $n$ increases, so to maximize this quotient, we want $n$ to have as many distinct prime factors as possible.
Furthermore, if $p < q$ for primes $p$ and $q$, then $$\frac{p}{p-1} > \frac{q}{q-1}$$ Put simply, this means that smaller prime factors will lead to a larger $n/\phi(n)$. These two facts suggest we should try numbers that are the product of the first several primes, which are called primorials. Our answer then is the largest primorial less than 1000000: $$2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 = 510510$$
Alternatively, you can just ask SageMath - its implementation of $\phi(n)$ is fast enough to brute force this problem. However, you might run into difficulties writing your own implementation that's this fast.
max(range(1, 1000001), key=lambda n: n / euler_phi(n))
510510
Relevant sequences¶
Copyright (C) 2025 filifa¶
This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International license and the BSD Zero Clause license.