Finding Fibonacci sequence in C#. [Project Euler Exercise]

Question

I'm having some trouble with this problem in Project Euler.

Here's what the question asks:

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, ... Find the sum of all the even-valued terms in the sequence which do not exceed four million.

My code so far: EDITED WITH NEW CODE THAT STILL DOESN'T WORK.

static void Main(string[] args)
{
    int a = 1;
    int b = 2;
    int Container = 0;
    int Sum = 0;

    while (b < 4000000)
    {
        if (a % 2 == 0)
        {
            Container += a;
        }

        Sum = a + b;
        a = b;
        b = Sum;
    }

    Container += b;

    Console.WriteLine(Container.ToString());
    Console.ReadLine();
}

Answer 1

One of the fun feature in C# is the "yield" keyword, which is very useful for this kind of thing:

IEnumerable<int> Fibonacci()
{
   int n1 = 0;
   int n2 = 1;

   yield return 1;
   while (true)
   {
      int n = n1 + n2;
      n1 = n2;
      n2 = n;
      yield return n;
   }
}

long result=0;

foreach (int i in Fibonacci().TakeWhile(i => i<4000000).Where(i => i % 2 == 0))
{
    result+=i;
}
Console.WriteLine(result);

The "traditional" recursive Fibonacci implementation is problematic here because it throws away all the work done along the way to the last requested term. You would have to call such a function over and over in a loop, which would duplicate a lot of work, or you could start with that implementation and add an argument to the recursive function to build up the desired sum result as the final fibonacci term is calculated. I like this much better, because it's still a general purpose fibonacci sequence at the core, rather than one you had to re-write or specialize.

Another approach is to use events (delegates) in a traditional implementation to call a separate method as each term is completed, but as I still like the iterator method better I'll leave the delegate option as an exercise for the reader.

Answer 2

Your problem is not that your code contains a bug; your problem is that your code contains a bug and you don't know how to find it. Solve the second problem first, and then you won't need to ask us when you have a bug, you'll be able to find it yourself.

Learning how to find bugs is hard and takes a lot of practice. Here's how I would approach this problem.

I'd start by simplifying the problem down to something I could do myself. Instead of "what's the sum of the even fib numbers that do not exceed four million?" I'd ask "what's the sum of the even fib numbers that do not exceed 40?" That's easy to work out by hand -- 2 + 8 + 34 = 44.

Now run your program in a debugger, stepping through each line, and see where things go wrong. Does your program actually add up 2, 8 and 34? And if so, does it get the correct result?

Answer 3

int sum = 2;
for(int f1 = 1, f2 = 2, f3 = 0; !((f3 = (f1 + f2)) > 4000000); f1 = f2, f2 = f3)
    sum += f3 * (~f3 & 1);

Answer 4

I think the question is written to say that you would add all the even numbers together while the numbers in the sequence don't exceed four million, meaning you would add 3,999,992.

Answer 5

You're checking both a and b on every iteration. So that means you're double counting almost everything.

Edit:

Ok, I see your update. This is pretty basic debugging, and you should really learn to try it yourself. Think about what the values of a and b are when your loop condition stops being true.

Answer 6

Joel, I wrote a very some similiar code; I'm posting it anyways:

static IEnumerable<int> Fibonacci(int maximum)
{
    int auxiliar = 0;
    int previous = 0;
    int current = 1;
    while (current < maximum)
    {
        auxiliar = previous;
        previous = current;
        current = auxiliar + current;
        yield return current;
    }
}

Console.WriteLine(Fibonacci(4000000).Where(number => number % 2 == 0).Sum());

Answer 7

The trickier way:

//1: Allow declaring of recursive functions
private delegate Func<T, R> FuncRec<T, R>(FuncRec<T, R> f);
static Func<T, R> RecFunction<T, R>(Func<Func<T, R>, Func<T, R>> f)
{
    FuncRec<T, R> funcRec = r => t => f(r(r))(t);
    return funcRec(funcRec);
}

//Define the factorial function
public static readonly Func<ulong, ulong> Fibonacci 
        = RecFunction<UInt64, UInt64>(fib => n =>
            (n == 1 || n == 0)
            ? n
            : fib(n - 1) + fib(n - 2)); 

//Make a "continous" version
static IEnumerable<ulong> ContinousFibonacci()
    {
        ulong count = 0;
        while(true)
        {
            ulong n = Fibonacci(count);
            count++;
            yield return n;
        }
    }

//Linq result
static void Main(string[] args)
    {


        ulong result = ContinousFibonacci()
            .TakeWhile(r => r < 4000000)
            .Where(IsEven)
            .Aggregate<ulong, ulong>(0,(current, s) => (s + current));

        Console.WriteLine(result);
        Console.ReadLine();

    }

///The Functional-Style method of allowing one to create recursive functions such as above was made by Bart De Smet. See http://bartdesmet.net/blogs/bart/archive/2009/11/08/jumping-the-trampoline-in-c-stack-friendly-recursion.aspx

Answer 8

Here's a nice way to find Fibonnaci numbers.

IEnumerable<BigInteger> Fibs()
{
    for(BigInteger a = 0,b = 1;;b = a + (a = b))
        yield return b;
}

Answer 9

     // count(user input) of Fibonacci numbers   
        int[] array = new int[20];
        array[0] = 0;
        array[1] = 1;

        Console.WriteLine(array[0] + "\n" + array[1]); 

        for (int i = 2; i < 20; i++)
        {
            array[i] = array[i - 1] + array[i - 2];
            Console.WriteLine(array[i]); 
        }