Sum of Fibonacci numbers

Question

Hi,

I'm rather new to Haskell. The problem is to find the sum of all even Fibonacci numbers not greater than 4 million. I can't use lists.

If I understand correctly, the below solution is wrong, because it uses lists:

my_sum = sum $ filter (odd) $ takeWhile (< 4000000) fibs

Where fibs is the list of all Fibonacci numbers.

Somehow, I find it difficult not to think in Haskell in terms of lists. Could anyone guide me to a solution to this problem?

Regards

EDIT:

If anyone is interested, I've solved this problem. Here is the code (very clumsy-looking, but works nevertheless):

findsum threshold = findsum' 0 1 0 threshold


findsum' n1 n2 accu t 
| n2 > t    = accu
| odd n2    = findsum' n2 n3 accu t 
| otherwise = findsum' n2 n3 accu2 t
where
    n3 = n2 + n1
    accu2 = accu + n2

Answer 1

You can do this without a list, with a recursive solution, using continuation-passing style.

BTW running through all the fibonacci numbers and filtering out the odd ones is the slow way to solve this problem.

Answer 2

You might find it easier to build this in excel and then figure the code out from there. It is pretty easy to do this in excel. Just put 1 in the first cell and put 1 just below it. Then make every cell below that add the two above it. (ie, cell a3 contains =A1+A2). Make the next column contain only even values "ie, if(mod(a3,2)==0,a3,0)". Next, put your running sum in the third column. Based on that you should be able to come up with the recursive solution.

Another way is to start with the problem. You only want a total which screams for an accumulator.

sumFib :: Integer -> Integer
sumFib threshold = sumFib' 1 1 0 threshold

sumFib' :: Integer -> Integer -> Integer -> Integer -> Integer
sumFib' n1 n2 acc threshold

You can see the signatures of my functions above. I built a pretty front end that takes a threshold (4,000,000) to decide when to quit building fibonacci numbers. Then I pass this plus the first 2 fibonacci numbers and an accumulator into the worker function "sumFib" which does the recursion. Voila...the answer, "4613732", without a list....

n1 is the n-1 fibonacci number and n2 is the n-2 fibonacci number.

Hope that helps.

EDIT: here is my full solution:

sumFib :: Integer -> Integer
sumFib threshold = sumFib' 1 1 0 threshold

sumFib' :: Integer -> Integer -> Integer -> Integer -> Integer
sumFib' n1 n2 acc threshold
     | n1 > threshold = acc
     | otherwise = sumFib' (n2+n1) n1 newAcc threshold
            where newAcc = if n1 `mod` 2 == 0
                               then n1 + acc
                               else acc

Answer 3

Again, a non-example for how useful computers can be:

You can do this without a computer!

1st observation: Every third Fibo-number is even, the first even Fibo-number is F_3=2

Indeed: odd+odd=even; odd+even=odd; even+odd=odd, which already closes the circle

2nd observation: F_3 + F_6 + F_9 + ... + F_{3k} = 1/2 (F_{3k+2} - 1)

By Induction: F_3 = 2 = 1/2 (5 - 1) = 1/2 (F_5 - 1)

F_3 + F_6 + ... + F_{3k+3} = 1/2 (F_{3k+2} - 1) + F_{3k+3} = 1/2 (F_{3k+2} + 2F_{3k+3} -1) = 1/2 (F_{3k+4} + F_{3k+3} -1) = 1/2 (F_{3k+5} -1)

3rd observation: The sum will have 1333333 summands, the last one being the 3999999-th Fibo-number.

4th observation: F_n = 1/sqrt(5) * (phi^n - (1-phi)^n)

Proof by Wikipedia

Now, we can put the parts together: F_3 + F_6 + ... + F_3999999 = 1/2 (F_4000001 - 1) = 1/2 1/sqrt(5) (phi^4000001 - (1-phi)^4000001) - 1/2 = int(1/2 1/sqrt(5) phi^4000001)

Here int is the integer part. The last step works, because -1 < 1-phi < 0 and so (1-phi)^4000001 nearly vanishes. You might want to use a calculator to get a numerical value.