7 de noviembre de 2013

Even Fibonacci numbers - Project Euler, problema 2

El problema es el siguiente:
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. 
No es difícil observar que los números de fibonacci pares forman la siguiente relación de recurrencia:
$E_{n+1}=4E_{n}+E_{n-1}$
Con $E_{1}=2$ y $E_{2}=8$
Sabiendo esto el método es prácticamente obvio:

E(1)=2;
E(2)=8;
S=E(1)+E(2);
i=2;
while S<=4000000
 i+=1;
 E=[E E(i-2)+4*E(i-1)];
 S+=E(i);
end
S