Project Euler 2: Sum of Even Fibonacci Numbers

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, \ldots$

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

The code generates Fibonacci numbers until it reaches the value of four million. The code then sums the even numbers in the sequence.

The intuitive way to calculate Fibonacci numbers is to use a recursive function. This function calls itself until it reaches the first two numbers.

ProjectEuler

  ## Project Euler 2: Sum of Even Fibonacci Numbers

  ## Recursive function

  fib <- function(n) {
      if (n <= 2) return(1)
      return(fib(n - 1) + fib(n - 2))
  }
  
  fib(15)

This function calculates the \(n^{th}\) Fibonacci number by calling itself with a reduced index until it reaches 1. Recursive functions are, however, very memory hungry and not very fast. A much faster method is to create a vector of Fibonacci numbers and add the even ones. The code below generates Fibonacci numbers until it reaches the value of four million. The code then sums the even numbers in the sequence.

  ## Sequential function

  fib <- c(1, 2)

  while (max(fib) < 4E+06) {
      len <- length(fib)
      fib <- c(fib, fib[len - 1] + fib[len])
  }
  
  answer <- sum(fib[fib %% 2 == 0])
  print(answer)

A series of R packages exist to generate Fibonacci numbers. The GMP package for Multiple Precision Arithmetic provides the fibnum() function to calculate the n^th Fibonacci number. This package is also able to work with huge numbers. Using this package is much faster than the base R code used above. Interestingly, the GMP library uses tables for Fibonacci numbers up to twelve quintillion (10¹⁸).

  # Using the GMP Package

  library(gmp)
  i <- 1

  answer <- 0
  fib <- fibnum(i)

  while (fib <= 4E6) {
    if (fib %% 2 == 0) {
      answer <- answer + fib
    }
    i <- i + 1
    fib <- fibnum(i)
  }

  print(answer)

An analytical solution prevents using recursion and a brute force method to find the answer. Binet's formula for the n^th Fibonacci number lets us determine a Fibonacci number without recursion:

$$F_n=\frac{\varphi^n-\frac{1}{(-\varphi)^n}}{\sqrt{5}}$$

We know that $\varphi$ is the Golden Ratio, so we can simplify this formula:

$$F_n\sqrt{5}=\frac{(1+\sqrt{5})^n}{2^n}$$

This formula results in a simple function to generate a sequence of Fibonacci numbers:

  ## Analytical solution

  binet <- function(n) {
    round((((1 + sqrt(5))^n) / 2^n) / sqrt(5))
  }

  binet(1:10)

The inverse of the Binet formula gives us:

$n=\left[ \log_\phi \sqrt{5}(F_n-\frac{1}{2}) \right]$ holds for all $n\ge 3$

This formula allows us to work out which Fibonacci number is less than or equal to 4 million:

  phi <- (1 + sqrt(5)) / 2

  n_4e6 <- floor(log(sqrt(5) * (4E6 - 0.5), base = phi))

Using this formula, we find that the first 33 Fibonacci numbers are equal or less than four million. Next step is to sum all the even numbers.

According to the Online Encyclopedia of Integer Sequences (lemma A014445), every third Fibonacci number is even. We can now use Binet's formula to sum every third Fibonacci number.

  sum(binet(seq(3, n_4e6, 3)))

As seen on R Bloggers