Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
偶斐波那契数
斐波那契数列中的每一项都是前两项的和。由 1 和 2 开始生成的斐波那契数列的前 10 项为：
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
考虑该斐波那契数列中不超过四百万的项，求其中为偶数的项之和。
根据斐波那契数列公式 f(n+2) = f(n+1) + f(n) 从第 1 项求到第四百万项即可：
(named-let f ((i 1) (j 1) (sum 0))
(cond
((> j 4000000) sum)
((cl-evenp j) (f j (+ i j) (+ sum j)))
(t (f j (+ i j) sum))))
;; 4613732由于奇奇得偶，奇偶得奇，偶偶得偶，容易观察得出以下规律：
1 1 2 3 5 8 13 21 34 55 89 144
a b c a b c a b c a b c可见从第一项开始以 3 个数为 1 组，每组的最后一个数都是偶数，我们也可以如此实现：
(named-let f ((a 1) (b 1) (c 2) (sum 0))
(cond
((> sum 4000000) sum)
(t
(setq a1 (+ b c)
b1 (+ a1 c)
c1 (+ a1 b1))
(f a1 b1 c1 (+ sum c)))))
;; 4613732进一步，我们可以推导出步长为 3 的斐波那契数列子列：
F(n) = F(n-1) + F(n-2)
= F(n-2) + F(n-3) + F(n-2) = 2F(n-2) + F(n-3)
= 2(F(n-3) + F(n-4)) + F(n-3) = 3F(n-3) + 2F(n-4)
= 3F(n-3) + F(n-4) + F(n-5) + F(n-6)
= 4F(n-3) + F(n-6)
G(n) = 4G(n-1) + G(n-2) G(1)=2 G(2)=8根据这个新数列公式，有如下代码：
(named-let f ((a 0) (b 2) (sum 0))
(cond
((> b 4000000) sum)
(t (f b (+ (* b 4) a) (+ sum b)))))
;; 4613732