Problem 70( 互いに素の並び替え [Totient permutation])
オイラーのトーティエント関数 φ(n) [φ関数と呼ばれることもある] は、n に対して互いに素である、 n より小さい数の数を決定するのに使用されます。
例えば、1、2、4、5、7、8はすべて9より小さく、9に対して相対的に素であるため、φ(9)=6となります。
1という数は、すべての正の数に対して相対的に素であると考えられるので、φ(1)=1です。
興味深いことに、φ(87109)=79180であり、87109は79180の並べ換えであることがわかります。
φ(n) が n の並べ換えであり、n/φ(n) が最小となる n の値、1 < n < 10^7 はいくつか。