Sum of even fibonacci numbers

Question

This is a Project Euler problem. If you don't want to see candidate solutions don't look here.

Hello you all! I'm developing an application that will find the sum of all even terms of the fibonacci sequence. The last term of this sequence is 4,000,000 . There is something wrong in my code but I cannot find the problem since it makes sense to me. Can you please help me?

using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
           long[] arr = new long [1000000] ;
           long i= 2;
           arr[i-2]=1;
           arr[i-1]=2;
           long n= arr[i];

           long s=0;
            for (i=2 ; n <= 4000000; i++)
            {                    
                arr[i] = arr[(i - 1)] + arr[(i - 2)];
            }
            for (long f = 0; f <= arr.Length - 1; f++)
            {
                if (arr[f] % 2 == 0)
                    s += arr[f];
            }
            Console.Write(s);
            Console.Read();                
        }
    }
}

Answer 1

try this (and use this for your big integer requirements: http://intx.codeplex.com/Wikipage ) :

using System;
using System.Collections;
using System.Linq;
using System.Collections.Generic;

using Oyster.Math;

namespace Application
{


public class Test
{

    public static void Main()
    {    
        IntX even = 0;
        Console.WriteLine("Sum of even fibonacci {0}\n", 
            Fibonacci(20).Where(x => x % 2 == 0).Sum());
        Console.WriteLine("Sum of odd fibonacci {0}", 
            Fibonacci(20).Where(x => x % 2 == 1).Sum());

        Console.Write("\nFibonacci samples");
        foreach (IntX i in Fibonacci(20))
            Console.Write(" {0}", i);

        Console.ReadLine();

    }

    public static IEnumerable<IntX> Fibonacci(int range)
    {
        int i = 0;

        IntX very = 0;       
        yield return very;
        ++i;

        IntX old = 1;       
        yield return old;
        ++i;

        IntX fib = 0; 
        while (i < range)
        {
            fib = very + old;
            yield return fib;
            ++i;

            very = old;
            old = fib;                
        }

    }
}


public static class Helper
{
    public static IntX Sum(this IEnumerable<IntX> v)
    {
        int s = 0;
        foreach (int i in v) s += i;
        return s;
    }
}

}

Sample Output:

Sum of even fibonacci 3382

Sum of odd fibonacci 7563

Fibonacci samples 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

Answer 2

I'll admit that I would do this entirely differently. I would probably use the paired sequence of Lucas and Fibonacci numbers, plus the simple formulas

F(n+a) = (F(a)*L(n) + L(a)*F(n))/2

L(n+a) = (5*F(a)*F(n) + L(a)*L(n))/2

Note that only every third Fibonacci number is even. So since F(3) = 2, and L(3) = 4, we get

F(n+3) = L(n) + 2*F(n)

L(n+3) = 5*F(n) + 2*L(n)

Now just sum the terms.

(edit: There is an even easier solution to this, that does rely on some mathematical sophistication to derive, or some knowledge of the Fibonacci sequence and identities for that sequence, or perhaps a search through the encyclopedia of integer sequences. Sadly, any more than this hint seems inappropriate for a PE problem, so I'll leave that solution in the margins of this note. Thus, the sum of the first k even Fibonacci numbers is...)

Answer 3

Change the first for loop to this:

for (i = 2; arr[i - 1] < 4000000; i++)

Answer 4

Use this: http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression

Third identity This identity has slightly different forms for Fj, depending on whether j is odd or even. The sum of the first n − 1 Fibonacci numbers, Fj, such that j is odd, is the (2n)th Fibonacci number.

The sum of the first n Fibonacci numbers, Fj, such that j is even, is the (2n + 1)th Fibonacci number minus 1.

[16]

The only problem is potential loss of precision when you raise phi to the (2n + 1)th power.

Answer 5

In this section:

       long n= arr[i];

       long s=0;
        for (i=2 ; n <= 4000000; i++)
        {

            arr[i] = arr[(i - 1)] + arr[(i - 2)];
        }

You've only assigned n once; n never updates, so your loop will never terminate.

n is not bound to i; n is set to arr[2] because i was 2 at that point. So, i will be 3 from the first iteration of the loop forever.

To fix this, one approach would be to get rid of n altogether and make your loop condition

for (i = 2; arr[i] <= 4000000; i++)