{-
Project Euler
** Problem 2
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.
-}
{-
Solution methods:
1. Brute force: Should be fun with Haskell. Lazy evaluation affords infinte lists.
2. There is a direct approx. formula for the n'th element, which will prove very useful here:
Fib(n) = (phi^n - (-phi)^n )/ sqrt(5)
phi = (1+sqrt(5) )/2 ; (-phi) = (1-sqrt(5) )/2
since (-phi)<1, when you do the ^n, it vanishes very quickly.
So, Fib(n) ~= floor [ ( phi^n)/sqrt(5) ] (this is for starting with n=0,1,2,...)
So let's do two things:
1. Fib(n)<4000000 ==> n*ln(phi) = ln(4000000) + ln(sqrt(5))
==> n = 16.00 / ln(1.618) = 33.2 ==> n=33 is the largest we need to consider
2. And, we note that the sum we are looking for is only of Fib(0), Fib(3), Fib(6), and so on.
Namely: sum_k=0^k=11 floor{ (phi)^(3*k)/sqrt(5)}
This is geometric series, with q=phi^3.
sum_k=0^k=11 Fib(n) = { ( 0 - (phi)^(3*(36)))/(1-phi^3) }/sqrt(5)
-}
fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)] :: [Int]
fibs1 = 0 : 1 : zipWith (+) fibs1 (tail fibs1)
fibs2 = 0 : 1 : [ a+b | a <- fibs2 ,b <- tail fibs2 ]
fibs3 = 0 : scanl (+) 1 fibs3
-- Testing (take 1000 fibs1) == (take 1000 fibs2)
main = do
putStrLn "Brute Force:"
print $ sum . filter (even) $ takeWhile(<= 4000000) fibs
putStrLn "Using Formula:"
let phi = (1+sqrt(5))/2 :: Double
print $ floor ( (0-phi^36) / (1-phi^3)/sqrt(5) )