Project Euler始めた

Project Euler解き始めました。自分の数学の勉強も兼ねて、できるだけプログラムでの力技の計算は避けようと思っています。どうしてもプログラミングが必要なやつは、あとでrowlで書こうと思ってます。

Problem 1

1000未満の3または5の倍数の和を求めよ

集合の加法定理が使えます。(3の倍数の和)+(5の倍数の和) - (15の倍数の和)ですから

となります。和の公式使って一発です。

Problem 2

4000,000以下のフィボナッチ数のうち偶数の物の和を求めよ。

書き出してみると

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

なので3n項目が偶数になる事がわかります。帰納法で証明できます。
フィボナッチ数列の一般項は

ですから偶数の項は

です。等比数列の和の公式を使って

が求める和です。ここで一般項、和ともに第２項の絶対値は0.5未満ですから、第１項だけ計算してもっとも近い整数に丸めれば答えが出ます。
f(3n) <= 4000,000となるnも対数つかって求められます。従ってRubyでの解答は以下のようになります。

include Math
SQRT5 = sqrt(5)
PHI3 = ( (1 + SQRT5)/2 )**3

n = ( log(4000_000 * SQRT5) / log(PHI3) ).floor # 項数
puts ((PHI3**(n+1)-1) / (SQRT5 * (PHI3 - 1))).round  # 和