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)$最小的一个。