Project Euler – Problem 2

Written by on 17 September 2010

Topics: Project Euler

The problem description of Problem 2 of Project Euler reads

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.

Before heading on with a solution, I will make a small comment on the problem formulation. Usually the first two numbers in the Fibonacci sequence is defined as F1 = F2 = 1. But that is just nitpicking and wont change anything in the solution.

In general the n’th number in the Fibonacci sequence is defined as Fn = Fn-1 + Fn-2, so we can make forward iteration on the problem.

A lot more on the sequence and its properties are found here.

Another consideration we might make, is how big can the solution be. A very conservative upper bound, is to use the formula derived from Problem 1 for the sequence of all numbers N*(N+1)/2, with N=4,000,000, that gives us an upper bound on the solution of 8.000002 × 1012, a number which in C# is too large to store in an integer, but can easily be stored in a long, so that part of the problem should not cause much of a problem.

Brute forcing

Can it be brute forced? Yes it can… We have already established that the next number in the sequence is easy to calculate and we are looping at maximum 4 million times, in each loop we need to calculate the next number in the sequence, check if it is even and add the number to the result. That should be quite doable in one minute.

So lets try it

long fib1 = 1;
long fib2 = 1;
long result = 0;
long summed = 0;

while (result < 4000000) {
    if ((result % 2) == 0) {
        summed += result;
    }

    result = fib1 + fib2;
    fib2 = fib1;
    fib1 = result;
}

First I define two longs (fib1 and fib2) and initialise them to F1 and F2, I also initialize a result variable to hold the newly calculated Fibonacci number, and a summing variable.

Then I loop, until the calculated number exceeds 4,000,000. Inside the loop the code is a bit upside down. First the result variable is added to the sum if the result is even, and then the next number is calculated, which I wont use until the next iteration. The reason for this, is that we don’t want to add the result if it is greater than 4,000,000. We could have added a separate check for this, and exited the loop. But this code is cleaner I think.

At the bottom of the loop we do a bit of moving around to keep the fib1 and fib2 variables updated.

The result of running the code on my machine

The result of all even numbered Fibonacci numbers less than 4M: 4613732
Solution took 0 ms

On my computer it went so fast that it wasn’t really possible to time it, but then again, we need no more than F34 to exceed 4,000,000

Calculating only the even numbers

Even though the solution is really fast, there are several methods to speed up the calculation.

If we look at the Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

We may notice the pattern that every third number is even starting at F3, so if we can express Fn in terms of Fn-3, Fn-6 then we only has to deal with even numbers

We start out with

Fn = Fn-1 + Fn-2 =
Fn-2 + Fn-3 + Fn-3 +Fn-4 = (since Fn-1 = Fn-2 + Fn-3 and so on)
Fn-3 + Fn-4 + Fn-3 +Fn-3 +Fn-4 = 3Fn-3 + 2Fn-4 =
3Fn-3 + Fn-4 + Fn-5 + Fn-6) =
4Fn-3 + Fn-6 (since Fn-4 + Fn-5 = Fn-3)

So now we can make some code which is only dependent on the even numbers, and thus we do not have to to calculate odd numbers once the sequence is started.

Lets code…

long fib3 = 2;
long fib6 = 0;
long result = 2;
long summed = 0;

while (result < 4000000) {
    summed += result;

    result = 4*fib3 + fib6;
    fib6 = fib3;
    fib3 = result;
}

I have initialised the variables a bit differently. I am starting with the calculation of F6 which means I need to initialize Fn-3 = F3=2 and Fn-6= F0= 0. And the result is then already 2 since Fn-3 is already calculated.

There is no need to check if the result is even, since it is by definition. Other than that, the code is really straight forward.

Reducing the number of write operations

Right now I am making a bit of house keeping in the last part of the while loop. This is cause quite a few writes. No real problem, with such a few calculations. But at some point we might encounter a problem where the memory becomes a scarce resource, so lets see if we can limit the memory footprint the number of writes to the memory

long[] fib = {2,0};
int i = 0;
long summed = 0;

while (fib[i] < 4000000) {
    summed += fib[i];
    i = (i + 1) % 2;
    fib[i] = 4 * fib[(i + 1) % 2] + fib[i];
}

What I have done here is removed one of the longs, and replaced it with an integer counter. Furthermore, I have changed the storage variables to an array, so it is easier to address. So through the counter variable which runs from 0 to 1, I can change the variable I am writing to. On line 7 in the program I count i up, and the easy way to make a loop is the modulo operator.

On line 8 I perform the calculation deduced in the last section.

In this case, the solution makes almost no difference. The memory footprint has been reduces minimally, and I have removed one write instruction, but added a few more calculations. I doubt it is measurable, but now the method is covered, since I might want to use it again. If the calculations were not stored in longs, but rather large arrays, saving one of them would have been beneficial, and a method I would consider for use in high performance computing.

Closing remarks

I covered the brute force, a more clever brute force method, and a bit about lowering the amount of house keeping and lowering the footprint.

There are likely a multitude of other ways, to speed up the calculation, so feel free to ask questions or comment on the post.

22 Comments For This Post I'd Love to Hear Yours!

  1. bill says:

    hello, thanks for your comprehensive blog. I will be working through it and honing my C# skills along the way, Thanks again.

  2. Kristian says:

    Hi Bill

    Thank you for the compliment. I hope you take something new with you from the blog, then my goal has been fulfilled

    /Kristian

  3. tomekz says:

    Hello, after each project Euler problem solved on my own i’m always checking your blog to learn a better solution. Great stuff!

  4. Kristian says:

    Thanks for the compliment, that is what I believe the right way to use the blog. Getting a little extra once you figured it out yourself.

  5. Anonymous says:

    In C++, you can write shortly i = !i; instead of i = (i + 1) % 2; and fib[!i] instead of fib[(i + 1) % 2] .. C++ FTW 😛

  6. Akshat says:

    My JS code(brute force)-

    function fib(stack, n) {
    if(n == 0) {
    return 0;
    }
    if(n == 1) {
    return 1;
    }
    return stack[n – 1] + stack[n – 2];
    }

    var max = 4000000;
    var total = 0;
    var stack = [];

    for(var i = 0; i max) {
    break;
    }
    if(stack[i] % 2 == 0) {
    total += stack[i]
    }
    }

    console.log(total);

  7. Russell says:

    Working with C# and Visual Studio 2013 with .NET 4.5:

    I print my results with this:

    Console.WriteLine(“The sum of all even numbers in the Fibonacci Sequence is: ” + result);

    and the console gives me this:

    The sum of all even numbers in the Fibonacci Sequence is: 5702887

    instead of what you show above:

    The result of all even numbered Fibonacci numbers less than 4M: 4613732
    Solution took 0 ms

    I doubled checked my code and couldn’t find any errors, so I commented it out and copied yours, still get 5702887. I can’t quite understand why these numbers would be different given the exact same code.

    Might you be able to explain the discrepancy between our results?

  8. Kristian says:

    It is beacuse you should print out the “summed” variable.

  9. Beginner says:

    Hi! I’m just a beginner, but I think that your first code is only valid for 4000000. If we asked to do the same for the numbers below 1000000, you might get an error. Your code only worked because de next term (bigger than 4000000) is not even. If it was, you would have got the wrong total…You should put (fib1+fib2<4000000) instead of (result<4000000). Am I right?

  10. Kristian says:

    The Fibonacci sequence will always have the pattern “odd, odd, even” and then go on. So it will indeed work for any limit in this case.

  11. Sangeeta says:

    Hi whenever i am trying to debug after typing the code given above it doesnt show any ans. could you please help me with it?

    thank you 🙂

  12. Sangeeta says:

    O good god.. no i got it thank you 🙂 😀 …. n kudos for the good work 🙂
    very beneficial for beginners like me .. 🙂

  13. teen_boy says:

    clever tactics … I like it 🙂

  14. Annonymous says:

    public class Test {
    //fibonicci series

    public static void main(String args[]){

    int n=1;
    long f=0;
    long sec=1;
    while (n<40000){
    System.out.println(sec+f);
    sec=sec+f; //here the second is now equal to the sum so …sum-first=second
    f=sec-f;
    n++;
    }

    }

    }
    You can also save one long variable in this way.

  15. Punit Maurya says:

    The third method was excellent. Really it saves so much of the memory. Keep it up…

  16. Ahmet Gokdayi says:

    Many thanks. Your solutions are well explained.

  17. Pigna says:

    I think I found a little faster method:
    8 (second even fibonacci number) = 2 * 1(fib) + 3 * 2(fib)
    34 (third even fibonacci number) = 2 * 5(fib) + 3 * 8(fib)
    144 (fourth even fibonacci number) = 2 * 21(fib) + 3 * 34(fib)
    Therefore (sorry, I don’t know C++, it’s python):

    a = 1
    b = 2
    s = 0
    while b <= 4000000:
    	s += b
    	a,b = a*1+b*2,a*2+b*3
    print s
    
  18. Ronnie says:

    I think a simpler approach would be to use the golden ratio as the driver and noting that every 3rd fib number is even. No memory requirements nor cpu intensive.


    void Euler002() {
    const double golden_ratio = 1.618034;
    const double sqrt5 = ::sqrt(5.0);
    long fib = 0;
    long sum = 0;
    int i = 6;
    while ( sum < 4000000) {
    fib = static_cast((::pow(golden_ratio, i) - ::pow(1.0 - golden_ratio, i)) / sqrt5);
    sum += fib;
    i += 3;
    }
    std::cout << sum << std::endl;
    }

  19. t m says:

    I puddled around in libreoffice spreadsheet and found (or seemed to) that the SUM of all evens = SUM of all Values at N * 1/2.

    If that observation is correct (and it *seems* it is…), then another observation – the full SUM of N terms = N+2 – 1, then…

    all that was left to do is find the last term below 4 mil (N = 34) and apply the solution function to find (N+2 – 1)/2 => (F(35) – 1)/2

    So if correct that means that the only issue to solve is (efficiently) finding N = 33, rather than having to see the full fib sequence to *know* that… which shouldn’t be too hard if I didn’t feel like putting my feet up already. (And assuming I didn’t make any mistakes…)

  20. tm says:

    For the curious, my spreadsheet solution (with cell ‘pseudo variables) was simply:

    threshold = 4000000

    n=ROUND(LN(threshold * SQRT(5))/LN((1 + SQRT(5)) / 2))

    answer = (((POWER((1+SQRT(5))/2,n+2) – POWER((1-SQRT(5))/2,n+2)) / SQRT(5)) – 1)/2

    NB:
    answer = Sum of even terms below threshold
    , where reliability below 70 is problematic

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.