Project Euler : Problem 2 - Even Fibonacci numbers

Problem Statement : Even Fibonacci numbers

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

Concept and Theory

Another great problem and another sweet calculations, which one can do in couple of minutes by hand itself. The concept behind this is Fibonacci series and its mysterious results.

Fibonacci series is simple you have two initial number and rest all of the numbers are sum of the previous two numbers, simple right ? For example, $1, \ 2, \ 3, \ 5, \ 8, \ 13, \ 21, \ 34, \ 55, \ 89, \dots$ is a Fibonacci series, first term, $F_1 = 1$ and $F_2 = 2$.

A general formula can be written from the above definition as follows:

$$F_1 = 1 \\ F_2 = 2 \\ F_n = F_{n-1} + F_{n-2} \ , \ n \geq \ 3$$

Note : Some people start Fibonacci Series with $F_1 = 0$ and $F_2 = 1$ and some starts with $F_1 = 1$ and $F_2 = 1$ both are equal. We will go as per the question given to us. {: .notice–info}{: .text-justify}

Lets begin with simple deductions and transforming a simple Fibonacci generator function using above recursive function.

1	1	2	3	5	8	13	21	34	55	89	144
A	B	C	A	B	C	A	B	C	A	B	C

One can observe that all the even terms in the Fibonacci series have 2 odd terms in between which is obvious and can be easily proved. All the $C$ terms are even. Hence one can carefully manipulate three temporary variables to just obtain the even terms. Thus,

$$a = b + c \\ b = c + a \\ c = a + b$$

All we have to do is maintain these variables and keep adding $c$ in our $sum$ till $c$ exceeds the limit.

Why not complicate stuff ?

Another useful result from Fibonacci series is Golden Ration.

In mathematics, two quantities are in the Golden Ratio if their ratio is the same as the ratio of their sum to the larger of the two quantities and is denoted by $\varphi$. The value of $\varphi$ , Golden ratio, for two numbers $a$ and $b$ is then,\

$$\varphi = \frac{a+b}{b} = \frac{a}{b} \\ \varphi = \frac{1+\sqrt{5}}{2} = 1.618033988749895\dots$$

(How do we get this?)

But, how the golden ration is related to Fibonacci series ? Remember $F_n = F_{n-1} + F_{n-2}$, got your “Ahaan!!!” moment, if not read along. Hint : What will be $F_n/F_{n-1}$? No worries,

$$\frac{F_n}{F_{n-1}} = \frac{F_{n-1} + F_{n-2}}{F_{n-1}}$$

Isn’t the above formula related to one defined by Golden Ratio? Yes it is(do the calculation or if you are not able to figure it out let me know). Hence,

$$\frac{F_n}{F_{n-1}} = \varphi$$

Lets get back to our problem. Can we find the ration between the two consecutive even terms of the Fibonacci series ?

$$\frac{F_n}{F_{n-1}} = \varphi \\ \frac{F_n}{F_{n-2}} = \frac{\frac{F_n}{F_{n-1}}}{\frac{F_{n-2}}{F_{n-1}}} = \frac{\varphi}{\frac{1}{\varphi}} = {\varphi}^2 \\ \frac{F_n}{F_{n-3}} = \frac{\frac{F_n}{F_{n-2}}}{\frac{F_{n-3}}{F_{n-2}}} = \frac{\varphi^2}{\frac{1}{\varphi}} = {\varphi}^3 = 4.23606797749979\dots \\ F_n = F_{n-3} \times {\varphi}^3$$

That’s it all we needed was this thing only. From the above one can say that the next even term will be $\varphi^3$ times the previous even term. We will be rounding the values obtained to its nearest integer to get an approx value.

Code

Simple way

/**
 *
 * A function to calculate the sum of all the even terms in a Fibonacci series
 * and the even term will not exceed the given limit.
 *
 * @param limit
 *            : given limit of maximum number below which we need to calculate
 *            the sum
 * @return : sum of all the even numbers of Fibonacci series
 */
public static long sumOfEvenTermsOfFibonacciSeries(long limit) {
  long res = 0L;
  long a = 1;
  long b = 1;
  long c = a + b;
  while (c < limit) {
    res += c;
    a = b + c;
    b = c + a;
    c = a + b;
  }
  return res;
}

Geeky way

public final static double PHI3 = Math.pow(((1 + Math.sqrt(5)) / 2), 3);

/**
 *
 * A function to calculate the sum of all the even terms in a Fibonacci series
 * and the even term will not exceed the given limit.
 *
 * @param limit
 *            : given limit of maximum number below which we need to calculate
 *            the sum
 * @return : sum of all the even numbers of Fibonacci series
 */
public static long sumOfEvenTermsOfFibonacciSeries(long limit) {
  long res = 0L;
  double first = 2L;

  while (Math.round(first) < limit) {
    res += Math.round(first);
    first = Math.round(first * PHI3);
  }
  return res;
}

Test Your Skills

Wanna try a harder version of the above problem ? Check this HackerRank problem.

Solution

The solution will remain same as above method $sumOfEvenTermsOfFibonacciSeries$, you just need to call it for each test case.

Note: My Geeky method won’t work for all test cases on Hackerrank. This is because of the double value precision goes down for $4 \times 10^16$.

References and Further Readings

• ProjectEuler
• Fibonacci sequence
• Golden Ratio