PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 72 / 分数の数え上げ

nとdを正の整数として分数 n/d を考えよう。 n < d かつ (n, d)=1 のものを真既約分数と呼ぶ。

d ≤ 8 について真既約分数を大きさ順に並べると次のようになる。

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

この集合は21個の要素をもつ。d ≤ 10^6について,真既約分数の集合は何個の要素を持つか?

Problem 72 - Project Euler

簡単なケースを考えてみましょう。

  • 分母が8の数の分子は8と互いに素
  • 分母が4の数の分子は4と互いに素

約分できないので,これらにダブりはありません。また,個数はオイラーのφ関数で簡単に求められます。