Project Euler

数学の問題をプログラムで解こうというプロジェクト。
正解すると他の回答者の投稿が見れます。

というわけでハマりました。
せっかくだからschemeでやってます。
毎日ちょっとずつやってますがプログラムより数学がむずい。
素因数分解とかフィボナッチ数列とか。
んでそのフィボナッチ数列が密かにマイブーム。
2つ目の問題に「(フィボナッチ)数列の項が400万を超えない範囲で、偶数の項の総和を求めよ」ってのがあって最初は

• 1 . 再帰で一個ずつ求めてリストに追加
• 2 . リミットに到達したらリストを返す
• 3 . リストから偶数だけ取り出して総和をとる

ってやってたのが。。。
φ(黄金比率)を使って「F(n)を求める式」と「nまでの総和をとる式」をwikipediaで発見&知り合いが「nまでの総和から偶数の総和を導く式」を教えてくれたのでコードを修正、せっかくだからうpします。

(fibo-sum-even (fibo-count 4000000))

;; nのb乗を返す
(define (expt n b)
  (let itr((count b) (product 1))
    (if (= 0 count)
	product
	(itr (- count 1) (* n product)))))

;; 黄金比率φ
(define phi (/ (+ 1 (sqrt 5)) 2))

;; フィボナッチ数列の第n項の値F(n)を返す
(define (fibo n)
  (inexact->exact (floor (+ (/ 1 2)
			    (/ (expt phi n)
			       (sqrt 5))))))

;; フィボナッチ数列の第n項までの総和を返す
(define (fibo-sum n)
  (- (fibo (+ n 2)) 1))

;; フィボナッチ数列の第n項までの偶数の総和を返す
(define (fibo-sum-even n)
  (cond ((= 0 (modulo n 3))
	 (/ (fibo-sum n) 2))
	((= 1 (modulo n 3))
	 (/ (fibo-sum (- n 1)) 2))
	((= 2 (modulo n 3))
	 (/ (fibo-sum (- n 2)) 2))))

;; フィボナッチ数列においてF(n)がmaxを越えない最大の項数nを返す
(define (fibo-count max)
  (let itr((count 0))
    (if (> (fibo count) max)
	(- count 1)