ホーム - Project Euler

Problem 70¶

Totient Permutation¶

Euler's totient function, $\phi(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, $\phi(9)=6$.
The number $1$ is considered to be relatively prime to every positive number, so $\phi(1)=1$.

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

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

トーティエント関数の置換¶

オイラーのトーティエント関数 φ(n) (ファイ関数とも呼ばれる) とは, n 未満の正の整数で n と互いに素なものの個数を表す. 例えば, 1, 2, 4, 5, 7, 8 は9未満で9と互いに素であるので, φ(9) = 6 となる.
1 は全ての正の整数と互いに素であるとみなされる. よって φ(1) = 1 である.

面白いことに, φ(87109)=79180 であり, 87109は79180を置換したものとなっている.

$1 \lt n \lt 10^7$ で φ(n) が n を置換したものになっているもののうち, n/φ(n) が最小となる n を求めよ.