Problem 69 の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• Problem 69 へ行く。

*[[Problem 69:http://projecteuler.net/problem=69]] 「トーティエント関数の最大値」 [#gac716a0]

オイラーのトーティエント関数, φ(&tex{n};) [時々ファイ関数とも呼ばれる]は, &tex{n}; と互いに素な &tex{n}; 未満の数の数を定める. たとえば, 1, 2, 4, 5, 7, そして8はみな9未満で9と互いに素であり, φ(9)=6.

|&tex{n};|互いに素な数|φ(&tex{n};)|&tex{n};/φ(&tex{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|

&tex{n}; ≤ 10 では &tex{n};/φ(&tex{n};) の最大値は &tex{n};=6 であることがわかる.

&tex{n}; ≤ 1,000,000で &tex{n};/φ(&tex{n};) が最大となる値を見つけよ.