Euler Problem 2: Even Fibonacci numbers

Sep 23, 2017 12:01 · 319 words · 2 minutes read R Python Project_Euler

Mathedemo

Euler 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.

Solutions

My solution to this problem is to generate a Fibonacci sequence with no value larger than the target, which is 4 million in this problem, then sum up all even numbers. To generalize this problem, I create a function that takes target \(n\) and return the sum of all even values in the Fibonacci sequence whose values do not exceed \(n\).

Solution in R

fibo_even_sum <- function(n) {
  fibo <- c(1, 2) # Initialize Fibonacci sequence
  
  while (max(fibo) < n) {
    len <- length(fibo)
    fibo <- c(fibo, fibo[len] + fibo[len - 1]) # Expand the sequence
  }
  
  if (fibo[length(fibo)] > n) {
    fibo <- fibo[-(length(fibo))] # Remove the last number in the sequence if it's larger than n
  } 
  
  sum(fibo[fibo %% 2 == 0])
}

fibo_even_sum(4e+06)

## [1] 4613732

Solution in Python

import numpy as np # Import numpy for numpy array data structure for vectorized computation

def fibo_even_sum(n):
    fibo = np.array([1, 2]) # Initialize Fibonacci sequence

    while max(fibo) < n:
        length = len(fibo)
        fibo = np.append(fibo, fibo[length - 1] + fibo[length - 2]) # Expand the sequence

    if fibo[len(fibo) - 1] > n:
        fibo = np.delete(fibo, len(fibo) - 1) # Remove the last number in the sequence if it's larger than n

    print(sum(fibo[fibo % 2 == 0]))
    
fibo_even_sum(4e+06)

## 4613732

The if statement inside the function removes the last element in the sequence if it’s larger than \(n\). The sum will be incorrect without this if statement for some circumstances. Please try \(n = 33\) without the if statement.