[Project Euler] Problem 2 「偶数のフィボナッチ数」

フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである.

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

数列の項の値が400万より小さい, 偶数値の項の総和を求めよ.

この問題もProblem 1と同じような方針で解きます.

1. 400万未満のフィボナッチ数のリストを求めます.
2. フィボナッチ数のリストから偶数のみを取り出します.
3. その和を求めます.

まず, フィボナッチ数のリストを求める手続きを定義します.

(define (fib-list n)
  (define (loop r a b)
    (if (< n a)
        (reverse r)
        (loop (cons a r) b (+ a b))))
  (loop () 1 2))

100未満の範囲で計算して方針に誤りが無いことを確認してから, 400万未満の範囲で計算します.

ようこそ DrRacket, バージョン 5.3.3 [3m].
言語: Pretty Big; memory limit: 128 MB.
> (fib-list 100)
(1 2 3 5 8 13 21 34 55 89)
> (filter even? (fib-list 100))
(2 8 34)
> (apply + (filter even? (fib-list 100)))
44
> (apply + (filter even? (fib-list 4000000)))
4613732

上限が400万ということなので, リストの要素数が増えそうなので末尾再帰にしてみましたが, 思ったよりも要素数が少なく残念な気分です.

> (fib-list 4000000)
(1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 
 4181 6765 10946 17711 28657 46368 75025 121393 196418
 317811 514229 832040 1346269 2178309 3524578)