Project Euler 2 - sinytのブログ

明日から帰省するので部屋の掃除などしてたら時間がない。

Project Euler Problem2。
問題文はここからProblem 2 - PukiWiki

このフィボナッチ数列の初項から第3項までは1,2,3となっている。
奇数と偶数の性質として、

奇数＋奇数＝偶数
奇数＋偶数＝奇数
偶数＋奇数＝奇数

というのがある。この性質とフィボナッチ数列の定義より、フィボナッチ数列においては偶数の項が２つおきにしか現われないということが分かる。*1
一般項はフィボナッチ数 - Wikipediaにある通りで、便宜的に初項から1,1,2とすると
$\sum_{i=1}^{\inf}\delta\left( F_{3i} < 4,000,000 \right)F_{3i}$
となる。

変形してみる。
$\sum F_{3i}=\sum \frac{\phi^{3i}-(-\phi)^{-3i}}{\sqrt{5}}$
$=\frac{1}{\sqrt{5}}\sum \phi^{3i}-\frac{1}{\sqrt{5}}\sum (-\phi)^{-3i}$
$F_{n}<4,000,000$ となる最大のnをNとすると、それぞれ等比数列の和となるので
$\frac{1}{\sqrt{5}}\left(\frac{1-\phi^{3N}}{1-\phi^3}-\frac{1-(-\phi)^{-3N}}{1-(-\phi)^{-3}}\right)$
どうしてもNが必要なので結局フィボナッチ数を逐次計算した方が早そう。誤差も怖いし。

てなわけで

fib1, fib2, fib3 = 1, 2, 3
sum = 0
while fib2 <= 4000000
  sum += fib2
  fib1 = fib2 + fib3
  fib2 = fib3 + fib1
  fib3 = fib1 + fib2
end
puts sum #=> 4613732

床関数を使って、 $\lfloor \frac{\phi^n}{\sqrt{5}}+\frac{1}{2} \rfloor$ でも表せるそうだが、普通に足した方が計算は速そう。

*1:と自力で考えてからWikipediaの同項に書かれてる事を知った。