Problem 69
Totient maximum
Euler’s Totient function, $\varphi(n)$ [sometimes called the phi function], is used to determine the number of numbers less than $n$ which are relatively prime to $n$. For example, as $1$, $2$, $4$, $5$, $7$, and $8$, are all less than nine and relatively prime to nine, $\varphi(9)=6$.
| $n$ | Relatively Prime | $\varphi(n)$ | $n/\varphi(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\ldots$ |
| $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/\varphi(n)$ for $n \le 10$.
Find the value of $n \le 1,000,000$ for which $n/\varphi(n)$ is a maximum.
欧拉总计函数与最大值
小于$n$且与$n$互质的正整数的数量记为欧拉总计函数$\varphi(n)$。例如，$1$、$2$、$4$、$5$、$7$和$8$均小于$9$且与$9$互质，因此$\varphi(9)=6$。
| $n$ | 互质的数 | $\varphi(n)$ | $n/\varphi(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\ldots$ |
| $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$ |
可以看出，对于$n \le 10$，当$n=6$时$n/\varphi(n)$取得最大值。
对于$n \le 1,000,000$，求使得$n/\varphi(n)$取得最大值的$n$。