« Project Euler - Problem 25 | トップページ | Project Euler - Problem 27 »

2009年7月 3日 (金)

Project Euler - Problem 26

問題はこちらをご覧ください。


基本的には分子をどんどん 10 倍していって分母で割ったときに余りが 1 になるところを探していきます。(余りが 1 になったところからまた繰り返しが始まるので……)

ただし、分母を素因数分解したときに、因子に 2 や 5 が含まれているとそのままの考え方では通用しなくなります。

そこで、循環節の長さを考える場合は、次のように分けて考えると分かりやすいと思います。

  1. 分母 d が 2 または 5 の因子を含まない場合
  2. 分母 d が 2 または 5 以外の因子を持たない場合
  3. その他の場合

1. の場合は (10 ** n).modulo(d) == 1 を満たす最小の n がそのまま循環節の長さになります。

例えば、分母 d が 7 の場合、n = 6 の時に上の式が成立します。実際の計算でも循環節はの長さは 6 になります。

2. の場合は割りきれてしまうので、循環節の長さは 0 となります。

3. の場合は、分母 d から 2 や 5 の因子を除去した数字で循環節を考えます。

例えば、分母 d が 15 だった場合、

1/15 = 1/(5 * 3) = 1/5 * 1/3 = 0.2 * 0.3333... = 0.0666...

となり、分母 d が 3 の時と同じ結果になります。


この問題を扱ったブログの中に「『フェルマーの小定理』を使えばいい……」といった言葉が散見されましたが、ここにも書いてあるように、「フェルマーの小定理」は分母が素数の時にしか適応できません。分母が合成数の場合まで考えるなら、「フェルマーの小定理」を拡張した「オイラーの定理」を使って考えるべきです。

まあ、「オイラーの定理」で検討すると、「分母が素数の時の方が、分母が合成数の時よりも循環節が長くなりそうだ」ということに気づくのですが……

ただし、「フェルマーの小定理」も「オイラーの定理」も循環節の最小値を保証しているわけではありません。

例えば分母が 11 の場合、「フェルマーの小定理」に当てはめると循環節の長さは "10" になりそうですが、実際には

1.0/11 = 0.090909...

となるので、循環節の長さは "2" になります。

ですから、「フェルマーの小定理」をそのまま適応するだけでは、この問題は解けません。地道に計算するしかないようです。

def count(m) m = m / 2 while m.even? m = m / 5 while m.modulo(5).zero? return 0 if m == 1 n = 10 c = 1 until n.modulo(m) == 1 n = n * 10 c = c + 1 end return c end max = [0, 0] 999.downto(2) do |i| break if i < max[1] c = count(i) max = [i, c] if c > max[1] end puts max[0]

「フェルマーの小定理」や「オイラーの定理」を検討すると、循環節の長さが分母の数以上になることはないことが分かります。

そこでこのコードでは、分母を大きい方から調べていって、分母が循環節の長さの最大値以下になった時点で計算を中断しています。

« Project Euler - Problem 25 | トップページ | Project Euler - Problem 27 »

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/45524625

この記事へのトラックバック一覧です: Project Euler - Problem 26:

« Project Euler - Problem 25 | トップページ | Project Euler - Problem 27 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ