Problem 70

Totient permutation

Euler’s Totient function, $\varphi(n)$ [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to $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$.

The number $1$ is considered to be relatively prime to every positive number, so $\varphi(1)=1$.

Interestingly, $\varphi(87109)=79180$, and it can be seen that $87109$ is a permutation of $79180$.

Find the value of $n$, $1<n<10^7$, for which $\varphi(n)$ is a permutation of $n$ and the ratio $n/\varphi(n)$ produces a minimum.

欧拉总计函数与重排

小于或等于$n$且与$n$互质的正整数的数量记为欧拉总计函数$\varphi(n)$。例如，$1$、$2$、$4$、$5$、$7$和$8$均小于$9$且与$9$互质，因此$\varphi(9)=6$。

$1$和任意正整数互质，所以$\varphi(1)=1$。

有趣的是，$\varphi(87109)=79180$，而$79180$恰好是$87109$的一个重排。

在$1<n<10^7$中，有些$n$满足$\varphi(n)$是$n$的一个重排，求这些取值中使$n/\varphi(n)$最小的一个。