Totient Maximum

Euler’s totient function, $\phi(n)$ [sometimes called the phi function], is defined as the number of positive integers not exceeding $n$ which are relatively prime to $n$. For example, as $1$, $2$, $4$, $5$, $7$, and $8$, are all less than or equal to nine and relatively prime to nine, $\phi(9)=6$.

$n$
Relatively Prime
$\phi(n)$
$n/\phi(n)$
2
1
1
2
3
1,2
2
1.5
4
1,3
2
2
5
1,2,3,4
4
1.25
6
1,5
2
3
7
1,2,3,4,5,6
6
1.1666…
8
1,3,5,7
4
2
9
1,2,4,5,7,8
6
1.5
10
1,3,7,9
4
2.5

It can be seen that $n = 6$ produces a maximum $n/\phi(n)$ for $n\leq 10$.
Find the value of $n\leq 1\,000\,000$ for which $n/\phi(n)$ is a maximum.

Given the mathematical task, it is quite obvious that we need to maximize the function $\frac{n}{\phi(n)}$. Euler’s Totient Function, $\phi(n)$, counts the positive integers up to a given integer $n$ that are relatively prime to $n$.

On examining the problem, observe that $n/\phi(n)$ gets maximized when $\phi(n)$ is minimized (keeping $n$ constant). To minimize $\phi(n)$, we need to maximize the count of numbers that divide $n$ (since less numbers would be relatively prime to $n$).

One way to do this is choose a number composed of a product of increasing primes. Given $n\leq 1\,000\,000$, a simple way to approach this would be to multiply primes until we get the largest result below 1,000,000:
$2 \times 3 = 6$
$2 \times 3 \times 5 = 30$
$2 \times 3 \times 5 \times 7 = 210$
$2 \times 3 \times 5 \times 7 \times 11 = 2310$
$2 \times 3 \times 5 \times 7 \times 11 \times 13 = 30030$
$2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 = 510510$

If we try to multiply by 19, the next prime number, the result is greater than 1,000,000, so the largest value of $n$ under 1,000,000 for which $n/\phi(n)$ is a maximum is $n = 510510$.

More Answers: