Project Euler Problem 2: Even Fibonacci numbers solution



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, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million,
find the sum of the even-valued terms.

My Algorithm

As explained in the problem statement, you can compute all Fibonacci numbers in an iterative way: F_i=F_{i-2}+F_{i-1}

My variables a and b stand for F_{i-2} and Fi-1 whereas next is Fi

#include <iostream>
int main()
unsigned int tests;
std::cin >> tests;
while (tests––)
unsigned long long last;
std::cin >> last;
unsigned long long sum = 0;
// first Fibonacci numbers
unsigned long long a = 1;
unsigned long long b = 2;
// until we reach the limit
while (b <= last)
// even ?
if (b % 2 == 0)
sum += b;
// next Fibonacci number
auto next = a + b;
a = b;
b = next;
std::cout << sum << std::endl;
return 0;
public final class p002 implements EulerSolution {
     public static void main(String[] args) {
          System.out.println(new p002().run());
      * Computers are fast, so we can implement this solution directly without any clever math.
      * Because the Fibonacci sequence grows exponentially by a factor of 1.618, the sum is
      * bounded above by a small multiple of 4 million. Thus the answer fits in a Java int type.
     public String run() {
          int sum = 0;
          int x = 1;  // Represents the current Fibonacci number being processed
          int y = 2;  // Represents the next Fibonacci number in the sequence
          while (x <= 4000000) {
               if (x % 2 == 0)
                    sum += x;
               int z = x + y;
               x = y;
               y = z;
          return Integer.toString(sum);
def fibs_up_to(t, a=1, b=2):
  while a < t:
    yield a
    a, b = b, a + b

fibs = fibs_up_to(4000000)
sum(n for n in fibs if n % 2 == 0)

#Brute force 2 - only generating even fibs (every third)
def even_fibs_up_to(t):
  a, b = 2, 3
  while a < t:
    yield a
    a, b = a + 2 * b, 2 * a + 3 * b

fibs = even_fibs_up_to(4000000)
sum(n for n in fibs)


The correct solution to the original Project Euler problem was found in less than 0.01 seconds on an Intel® Core™ i7-2600K CPU @ 3.40GHz. (compiled for x86_64 / Linux, GCC flags: -O3 -march=native -fno-exceptions -fno-rtti -std=gnu++11 -DORIGINAL)



Above code solves 5 out of 5 test cases (score: 100%)


5% Project Euler ranks this problem at 5% (out of 100%).

Hackerrank describes this problem as easy.

Hackerrank has strict execution time limits (typically 2 seconds for C++ code) and often a much wider input range than the original problem.
In my opinion, Hackerrank's modified problems are usually a lot harder to solve. As a rule thumb: brute-force is rarely an option.

Links best forum on the subject (note: you have to submit the correct solution first)

Code in various languages:

C# (written by Kristian Edlund)
C (written by eagletmt)
Java (written by Nayuki)
Javascript Even Fibonacci numbers.js (written by David Ernst)
Go (written by Frederick Robinson)
Mathematica (written by Nayuki)
Haskell (written by Nayuki)
Scala (written by Michael Bayne)
Perl (written by Gustaf Erikson)

Those links are just an unordered selection of source code I found with a semi-automatic search script on Google/Bing/GitHub/whatever.
You will probably stumble upon better solutions when searching on your own.
Maybe not all linked resources produce the correct result and/or exceed time/memory limits.

About the author

Add comment