Problem 70

Totient Permutation

Euler’s Totient function, $φ (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, $φ (9) = 6$ .

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

Interestingly, $φ (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 $φ (n)$ is a permutation of $n$ and the ratio $n / φ (n)$ produces a minimum.

欧拉总计函数与重排

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

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

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

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