Even Fibonacci Numbers -

Premise

Hi everyone, we are doing another Project Euler problem, the next one in line! The premise of the problem states:
Each number in a Fibonacci sequence is generated by adding the previous two numbers. By starting with 1 and 2, the first ten 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.

Solution

A Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, typically starting with 0 and 1. The sequence follows a pattern of 0, 1, 1, 2, 3, 5, 8, 13, and so on.

The first idea that fell on my mind is the old-fashioned brute-force way of solving it. We can create a loop that hits its limit at four million, and we can generate new numbers of the Fibonacci sequence inside every iteration. We just check the even ones, we add them together in a sum variable, and voila. Let us try it.

JavaScript

function evenFibonacci() {
    let fibonacciElement1 = 1;
    let fibonacciElement2 = 2;
    let limit = 4000000;
    finalSum = 0;
    
    while(fibonacciElement2 < limit) {
        if(fibonacciElement2 % 2 === 0) {
            finalSum += fibonacciElement2;
        }
        
        let fibonacciSum = fibonacciElement1 + fibonacciElement2;
        fibonacciElement1 = fibonacciElement2;
        fibonacciElement2 = fibonacciSum;    
        
    }
    return finalSum;
}

evenFibonacci();

Python

def even_fibonacci():
    fibonacci_element1 = 1
    fibonacci_element2 = 2
    limit = 4000000
    final_sum = 0
    
    while fibonacci_element2 < limit:
        if fibonacci_element2 % 2 == 0:
            final_sum += fibonacci_element2
        
        fibonacci_sum = fibonacci_element1 + fibonacci_element2
        fibonacci_element1 = fibonacci_element2
        fibonacci_element2 = fibonacci_sum
    
    return final_sum
    
even_fibonacci()

But it seems like this is not the only approach available. Let us repeat the first ten numbers of the Fibonacci sequence, and add another couple at the end, for testing’s sake, and we would get 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181. Let us extract even numbers from the list. 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181. It seems like all of these even numbers follow a mathematical rule.

2 * 4 + 0 = 8 \\ 8 * 4 + 2 = 32 \\ 34 * 4 + 8 = 144 \\ 144 * 4 + 34 = 610

Seems like the current even element of the Fibonacci sequence is retrieved by multiplying the previous one by 4 and adding the one that precedes it! Let us model this.

Javascript

function evenFibonacci() {
    let firstElement = 2;
    let secondElement = 8;
    let thirdElement = 34;
    let limit = 4000000;
    finalSum = firstElement + secondElement + thirdElement;
    
    while(finalSum < limit) {
        firstElement = secondElement;
        secondElement = thirdElement;
        thirdElement = secondElement * 4 + firstElement;
        
        finalSum += thirdElement;
        
    }
    
    return finalSum;
}

evenFibonacci();

Python

def even_fibonacci():
    first_element = 2;
    second_element = 8;
    third_element = 34;
    limit = 4000000;
    final_sum = first_element + second_element + third_element;
    
    while final_sum < limit:
        first_element = second_element;
        second_element = third_element;
        third_element = second_element * 4 + first_element;
        
        final_sum += third_element;
    
    return final_sum
    
even_fibonacci()

Facebook Tweet Pin LinkedIn