PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 69 / nとφ(n)の比

オイラーのファイ関数 φ(n) は n と互いに素な n 未満の数の数を表す。たとえば1, 2, 4, 5, 7, 8は9未満かつ9と互いに素であるから φ(9)=6 である。

n互いに素な数φ(n)n/φ(n)
2112
31,221.5
41,322
51,2,3,441.25
61,523
71,2,3,4,5,661.1666...
81,3,5,742
91,2,4,5,7,861.5
101,3,7,942.5

n ≤ 10 とき n/φ(n) は n=6 で最大値をとる。n ≤ 10^6 で n/φ(n) の最大値を与える n を求めよ。

Problem 69 - Project Euler


φ(n) はMathematicaに組み込まれていて,最大値はすぐに求められます。

では,対応する n は? 対話的に求めてみました。

f:id:variee:20170316011125p:plain

m=30で最大ですね。検算してみたら,あっていました。


追記(2017/04/20)

元記事で「対話的に~」と書いてあるのは多分,最大値を与える n の求め方をしらなかったからだと思います。今なら普通にできます。