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 F_{1} = F_{2} = 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 F_{n} = F_{n-1} + F_{n-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 × 10^{12}, 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 F_{1} and F_{2}, 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 F_{34} 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 F_{3}, so if we can express F_{n} in terms of F_{n-3}, F_{n-6} then we only has to deal with even numbers

We start out with

F_{n} = F_{n-1} + F_{n-2} =

F_{n-2} + F_{n-3} + F_{n-3} +F_{n-4} = (since F_{n-1} = F_{n-2} + F_{n-3} and so on)

F_{n-3} + F_{n-4} + F_{n-3} +F_{n-3} +F_{n-4} = 3F_{n-3} + 2F_{n-4} =

3F_{n-3} + F_{n-4} + F_{n-5} + F_{n-6}) =

4F_{n-3} + F_{n-6} (since F_{n-4} + F_{n-5} = F_{n-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 F_{6} which means I need to initialize F_{n-3} = F_{3}=2 and F_{n-6}= F_{0}= 0. And the result is then already 2 since F_{n-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.

cool!

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

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

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

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.

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 😛

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);

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?

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

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?

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.

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 🙂

O good god.. no i got it thank you 🙂 😀 …. n kudos for the good work 🙂

very beneficial for beginners like me .. 🙂

clever tactics … I like it 🙂

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.

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

Many thanks. Your solutions are well explained.

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):

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;

}

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…)

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

A mathematical approach (+ some Scala):

https://www.data-blogger.com/2016/07/24/summing-the-fibonacci-sequence/

Sum of all odd Fibonacci numbers as obtained with Python (v3.6.1)

>>> fib = 1

>>> fib2 = 2

>>> temp = 0

>>> total = 0

>>>

>>> while temp 0:

… total += temp

… temp = fib + fib2

… fib = fib2

… fib2 = temp

…

>>> print (total)

4613730

As indicated in the article, the sum of all even Fibonacci numbers is 4613732.

The difference of 2 is due to the fact that the Fibonacci is starting at 1 and not at 0 as it is more often used (1).

Then, we have to add 2 to 4613730.

___

Source:

1) Fibonacci number

https://en.wikipedia.org/wiki/Fibonacci_number

Correction: Sorry, one line is missing in my previous comment.

Sum of all odd Fibonacci numbers as obtained with Python (v3.6.1)

>>> fib = 1

>>> fib2 = 2

>>> temp = 0

>>> total = 0

>>>

>>> while temp 0:

… total += temp

… temp = fib + fib2

… fib = fib2

… fib2 = temp

…

>>> print (total)

4613730

Here is the complete text:

Sum of all odd Fibonacci numbers as obtained with Python (v3.6.1)

As indicated in the article, the sum of all even Fibonacci numbers is 4613732.

The difference of 2 is due to the fact that the Fibonacci is starting at 1 and not at 0 as it is more often used (1).

Then, we have to add 2 to 4613730.

Source:

1) Fibonacci number

https://en.wikipedia.org/wiki/Fibonacci_number

Fibonacci even numbers below 4000000

Fibonacci even numbers (cumulative values)

2, 8 (10); 34 (44); 144 (188); 610 (798); 2584 (3382); 10946 (14328);

46368 (60696); 196418 (257114); 832040 (1089154); 3524578 (4613732).

Fibonacci odd numbers below 4000000

Fibonacci odd numbers (cumulative values)

1, 1, 3, 5 (10); 13, 21 (44); 55, 89 (188); 233, 377 (798); 987, 1597 (3382);

4181, 6765 (14328); 17711, 28657 (60696); 75025, 121393 (257114);

317811, 514229 (1089154); 1346269, 2178309 (4613732).

I don’t know why, but you can find the next even number in the Fibonacci sequence by multiplying the previous even number by 4 and adding the previous even number to the result.

Examples :

( 2 • 4 ) + 0 = 8

( 8 • 4 ) + 2 = 34

( 34 • 4 ) + 8 = 144

…

( 832040 • 4 ) + 196418 = 3524578

Maybe that can help you to resolve the problem faster, or not, I’m not a programmer by the way.

I’d suggest using bitwise xor instead of modulo combined with incrementation, as it’s only a single operation.

`i ^= 1;`

This can be solved in O(log2(n)), assuming the function you use to calculate exponents has that time complexity.

First note that any Fibonacci number Fn can be calculated using the formula: Fn = (a^n – B^n)/sqrt(5) where a = (1 + sqrt(5))/2 and B = (1 – sqrt(5))/2

Based on that, we get:

Fn – a^n/sqrt(5) = B^n/sqrt(5)

Since 0 < |B| < 1, then 0 < |B^n| < 1, so

|Fn – a^n/sqrt(5)| = |B^n/sqrt(5)| < 1/sqrt(5) < 1/sqrt(4) = 1/2

Thus, F(n + 1) > a^(n + 1)/sqrt(5) – 1/2 > N >= Fn > a^n/sqrt(5) – 1/2

Solve for n and you get: n + 1 > ln((N + 1/2) * sqrt(5))/ln(a) > n

Thus we can find the n such that F(n + 1) > N >= Fn by solving floor(ln((N + 1/2) * sqrt(5))/ln(a)). Note, that this n might not be for an even Fibonacci number. However, as said in the post, every 3rd Fibonacci number is even, so simply subtract n % 3 from n to get the closest n such that n % 3 = 0 and N >= Fn.

Now we need to solve the summation of even numbers. Note that sum(Fi) from i = 1 to n is equal to F(n + 2) – 1. This can be proven through induction.

Let x = sum(F(3i)) from i = 1 to n/3 and let y = sum(Fi) from i = 1 to n. We want to solve x.

x = y – (F1 + F2 + F4 + F5 + …) = y – (F3 + F6 + …) = y – x = y/2

Therefore, sum(F(3i)) from i = 1 to n/3 = (F(n + 2) – 1)/2. As pointed out above, given any n, you can use a and B to find Fn, thus we can find the sum of all even numbers with this equation:

x = ((a^(n + 2) – B^(n + 2))/sqrt(5) – 1)/2

= ((((1 + sqrt(5))/2)^(n + 2) – ((1 – sqrt(5))/2)^(n + 2))/sqrt(5) – 1)/2

Here’s the code:

public double SumEvenFibonacciNumbers(double upTo)

{

double RootOfFive = Math.Sqrt(5);

double Alpha = (1 + RootOfFive) / 2;

double Beta = (1 – RootOfFive) / 2;

`int FibonacciIndex = (int)Math.Floor(Math.Log((upTo + 0.5) * RootOfFive) / Math.Log(Alpha));`

FibonacciIndex -= FibonacciIndex % 3;

`double FibonacciNumberNPlusTwo = (Math.Pow(Alpha, FibonacciIndex + 2) - Math.Pow(Beta, FibonacciIndex + 2)) / RootOfFive;`

return (FibonacciNumberNPlusTwo - 1) / 2;

}

I think Matrix exponentiation should easily work on the recurrence relation for even fib number .