オイラーのファイ関数 φ(n) は n と互いに素な n 未満の数の数を表す。たとえば1, 2, 4, 5, 7, 8は9未満かつ9と互いに素であるから φ(9)=6 である。
n 互いに素な数 φ(n) n/φ(n) 2 1 1 2 3 1,2 2 1.5 4 1,3 2 2 5 1,2,3,4 4 1.25 6 1,5 2 3 7 1,2,3,4,5,6 6 1.1666... 8 1,3,5,7 4 2 9 1,2,4,5,7,8 6 1.5 10 1,3,7,9 4 2.5 n ≤ 10 とき n/φ(n) は n=6 で最大値をとる。n ≤ 10^6 で n/φ(n) の最大値を与える n を求めよ。
φ(n) はMathematicaに組み込まれていて,最大値はすぐに求められます。
では,対応する n は? 対話的に求めてみました。
m=30で最大ですね。検算してみたら,あっていました。
追記(2017/04/20)
元記事で「対話的に~」と書いてあるのは多分,最大値を与える n の求め方をしらなかったからだと思います。今なら普通にできます。