(see projecteuler.net/problem=2)

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 F_{i-1} whereas next is F_{i}

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

# Benchmark

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)

# Hackerrank

see https://www.hackerrank.com/contests/projecteuler/challenges/euler002

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

# Difficulty

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

Hackerrank describes this problem as **easy**.

*Note:*

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

projecteuler.net/thread=2 – **the** best forum on the subject (*note:* you have to submit the correct solution first)

Code in various languages:

C# www.mathblog.dk/project-euler-problem-2/ (written by Kristian Edlund)

C github.com/eagletmt/project-euler-c/blob/master/1-9/problem2.c (written by eagletmt)

Java github.com/nayuki/Project-Euler-solutions/blob/master/java/p002.java (written by Nayuki)

Javascript github.com/dsernst/ProjectEuler/blob/master/2 Even Fibonacci numbers.js (written by David Ernst)

Go github.com/frrad/project-euler/blob/master/golang/Problem002.go (written by Frederick Robinson)

Mathematica github.com/nayuki/Project-Euler-solutions/blob/master/mathematica/p002.mathematica (written by Nayuki)

Haskell github.com/nayuki/Project-Euler-solutions/blob/master/haskell/p002.hs (written by Nayuki)

Scala github.com/samskivert/euler-scala/blob/master/Euler002.scala (written by Michael Bayne)

Perl github.com/gustafe/projecteuler/blob/master/002-Even-Fibonacci-numbers.pl (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.