DEV Community

Project Euler #2 - Even Fibonacci numbers

Peter Kim Frank on June 13, 2018

I had a blast reading through the many creative and varied approaches to solving Problem #1. There's something very fun and enlightening about see...

Read full post

Massimo Artizzu • Jun 13 '18 • Edited

Math to the rescue again!
To compute the n-th Fibonacci number, you can use the Binet formula:

$Binet's formula for Fibonacci's numbers$

where φ is the Golden Ratio, (1 + √5)/2. Also, it's given that f(0) = 0 and f(1) = 1, instead of having 1 and 2 as the first two Fibonacci's numbers.

In order to know which Fibonacci number is the highest below 4 million, we can solve by n... which isn't really easy. So, instead, we get to obtain a (pretty good) estimate by ignoring the second term (-1/φ)^n, which quickly approaches to 0, and solve:

$\frac{\varphi^n}{\sqrt{5}}\approx4\cdot10^6$
$\Rightarrow n = \left\lfloor \log_\varphi 4\sqrt{5} \cdot 10^6 \right\rfloor = 33$

In fact, f(33) = 3524578 and f(34) = 5702887.
Now, it's time to sum. First of all, let's notice that the even terms in the Fibonacci sequence happen once every three: f(0) = 0, f(3) = 2, f(6) = 8, f(9) = 34 and so on. So, we just have to sum every f(3 k) for k from 0 to 11. Using the known formula:

$\sum_{k=0}^n a^{hk} = \frac{a^{h(n+1)}-1}{a^h-1}$

and using a = φ, h = 3 and n = 11, we have:

$\sum_{k=0}^{11} f(3k) = \sum_{k=0}^{11}\frac{1}{\sqrt5}(\varphi^{3k}-(-\varphi^{-1})^{3k})$

$= \frac{1}{\sqrt5} \left(\sum_{k=0}^{11} \varphi^{3k} - \sum_{k=0}^{11}(-\varphi^{-1})^{3k}\right)$

$=\frac1{\sqrt5}\left(\frac{\varphi^{36}-1}{\varphi^3-1}-\frac{(-\varphi^{-1})^{36}-1}{-\varphi^{-3}-1}\right)=4613732$

So, more in general, using JavaScript (for example):

const SQ5 = 5 ** .5;
const PHI = (1 + SQ5) / 2;
function allEvenFibonacciUpTo(limit) {
  const highestIndexBelowLimit = Math.floor(Math.log(limit * SQ5) / Math.log(PHI));
  // I love expressive variable names, but the formula could get too long!
  const n = Math.floor(highestIndexBelowLimit / 3);
  return ((PHI ** (3 * n + 3) - 1) / (PHI ** 3 - 1)
    - ((1 - PHI) ** (3 * n + 3) - 1) / ((1 - PHI) ** 3 - 1)) / SQ5;
}

console.log(allEvenFibonacciUpTo(4e6)); // 4613731.999999999

Well... I guess we'll have to deal with some rounding problems 😅
But another O(1) solution, yay! 🎉

(By the way, -1/φ = 1 - φ if you were confused.)

Kushan Joshi • Jun 14 '18 • Edited

Ah nice to see maths, I came up with the same thing however with a different approach of using generator functions.

Let us forget about fibonacci and think of the even fibonacci as a new series. (I probably think there would be a mathematical way of deducing it, but I just used brute force to find it out)

series = 2, 8, 34, 144, 610, 2584...
34 = 8*4 + 2,
144 = 34*4 + 8,
610 = 144*4 + 34;
Number = 4 * (Previous Number) +  Previous Previous Number

So the recurrence relation for this series would be

F_n= 4F_n-1 + F_n-2.
To find out the Sum of n elements in this series (let's call this S_n), we can rewrite the recurrence relation like this:
4F_n-1 = F_n - F_n-2
and we can move all n's by 1:
4F_n = F_n+1 - F_n-1

Now we can use the same logic to finder other n's:
4F_n = F_n+1 - F_n-1
4F_n-1 = F_n - F_n-2
4F_n-2 = F_n-1 - F_n-3
4F_n-3 = F_n-2 - F_n-3
...
...
4F₄ = F₅ - F₃
4F₃ = F₄ - F₂
4F₂ = F₃ - F₁
4F₁ = 4F₁

For folks not familiar with this technique, we are simply doing to cancel out similar terms when we add all equations. (Note all items in pair are canceled out since x - x = 0).

4F_n = F_n+1 - ~~F_n-1~~
4F_n-1 = F_n - ~~F_n-2~~
4F_n-2 = ~~F_n-1~~ - ~~F_n-3~~
4F_n-3 = ~~F_n-2~~ - ~~F_n-3~~
...
...
4F₄ = F₅ - F₃
4F₃ = F₄ - F₂
4F₂ = F₃ - F₁
4F₁ = 4F₁

4F_n + 4F_n-1 + 4F_n-2 + ... + 4F₂ + 4F₁ = F_n+1 + F_n - F₂ + 3F₁

If you notice the left hand side is essentially equivalent to
4S_n

Now we can finally write the relation between sum and series as:

S_n= ( F_n+1 + F_n - F₂ + 3F₁ ) / 4

The point is this avoids the for loop for summing all the values. Go ahead and try substituting values and you will find this sums it up. You will have to use F(1) = 2 and F(2) = 8.

Now that we have removed one for loop, how do we get a direct formula for getting the F_n.

This involves a bit more complicated math(for adventurous folks visit austinrochford.com/posts/2013-11-0...).
In short the closed form for this recurrence relation is

And if you compute the roots and follow along the url I posted above, you will end up with this

This gives us a function to compute F_n .

Now we can combine our summing and this formula to get a simple O(1) arithmetic function to get the sum. Side note: Running a for loop will take much less brain time :P

Massimo Artizzu • Jun 14 '18

I applaud your solution, fellow math lover! 👏

Nested Software • Jun 14 '18 • Edited

These are really great solutions. I think it would be worthwhile for you to publish them as standalone articles. One quibble: I don't think this is O(1) since arithmetic operations are not constant time as a function of input, although I guess as long as we’re sticking with floating point numbers O(1) is probably valid.

edA‑qa mort‑ora‑y • Jun 14 '18

You're correct that addition is O(log N) for a number N, or O(log n) where n is the number of digits. The power function x^n also has a O(log N) time complexity if N is an integer (I presume it's also linear on number of significant bits).

Given fixed sized types on a computer though I believe most of these become constant time, as the inputs have a fixed upper limit on bits. It probably involves an unrolled loop, or fixed iterations on a CPU.

Massimo Artizzu • Jun 14 '18

Yes, indeed. I am in fact using just plain double precision numbers there, and they do take a fixed amount of ticks for common operations like those on a modern CPU.

I wouldn't be so certain if I used JavaScript's BigInt numbers (or rather, I would be certain of the opposite).

Thank you for the explanation!

Ali Spittel • Jun 13 '18

OOhh Project Euler problems are my favorite!

"""
Even Fibonacci numbers: Project Euler Problem 2
Solution in Python

https://projecteuler.net/problem=2

Takes 0.4s on my computer
"""
def fibonacci_sequence(n):
    numbers = [0, 1]

    while numbers[-1] < n:
        numbers.append(numbers[-1] + numbers[-2])

    return numbers


def sum_even_fibonacci_numbers(n):
    # O(N) Complexity
    sequence = fibonacci_sequence(n)
    sequence = [n for n in sequence if n % 2 == 0]
    return sum(sequence)

print(sum_even_fibonacci_numbers(4000000))

Priyansh Jain • Jun 15 '18

I tried timing your algorithm, with couple other implementations I wrote. One was recursive, one was iterative. Check this out.

# recursive
def recursive_fibonacci(num, prev_num, sum=0):
    if num % 2 == 0:
        sum += num
    if num < 4000000:
        return recursive_fibonacci(num + prev_num, num, sum)
    return sum

# iterative
def iterative_fibonacci(num, second_num):
    sum = 0
    while num < 4000000:
        if num % 2 == 0:
            sum += num
        temp = num
        num += second_num
        second_num = temp
    return sum

# Other
def fibonacci_sequence(n):
    numbers = [0, 1]

    while numbers[-1] < n:
        numbers.append(numbers[-1] + numbers[-2])

    return numbers


def sum_even_fibonacci_numbers(n):
    # O(N) Complexity
    sequence = fibonacci_sequence(n)
    sequence = [n for n in sequence if n % 2 == 0]
    return sum(sequence)

import time

start_time_recursive = time.time()
print(recursive_fibonacci(1, 1))
print("--- Recursive %s seconds ---" % (time.time() - start_time_recursive))

start_time_iterative = time.time()
print(iterative_fibonacci(1, 1))
print("--- Iterative %s seconds ---" % (time.time() - start_time_iterative))

start_time_other = time.time()
print(sum_even_fibonacci_numbers(4000000))
print("--- Other %s seconds ---" % (time.time() - start_time_other))

The output was interesting!

Phil Nash • Jun 14 '18

I went for what I thought was an interesting solution with Ruby this time. It uses a lazy enumerable over an infinite range and calculates the sum and the fibonacci numbers until the end condition is met.

def sum_even_fibonacci_numbers_up_to(max)
  range = 1..Float::INFINITY
  sum = 0
  last_two_fibs = [0,1]

  range.lazy.take_while do
    next_fib = last_two_fibs[0] + last_two_fibs[1] 
    sum += next_fib if next_fib % 2 == 0
    last_two_fibs = [last_two_fibs[1], next_fib]
    next_fib < max
  end.force

  sum
end

sum_even_fibonacci_numbers_up_to(4_000_000)
# => 4613732

This uses constant space, so does not compute an array of fibonacci numbers, just holds the latest two and the current sum. It runs in O(n) time and for 4,000,000 took less than 0.2s on my Macbook Pro.

Ross Henderson • Jun 15 '18

SQL

I have an answer, but I'm not 100% happy with it. It's not dynamic enough, but I need to do some more digging into Cycles it seems :)

with FIBONACCI (i, FIBO, PREV) as 
(
   select  
      1 i, 0 FIBO, cast(null as number) PREV 
   from 
      DUAL
   union all
   select 
      f1.i + 1  i, f1.FIBO + nvl(f1.PREV,1) FIBO, f1.FIBO PREV
   from 
      FIBONACCI f1
   where 
      f1.i < 35
)

select 
   sum(FIBO) as "Answer"
from 
   FIBONACCI
where 
   mod(FIBO, 2) = 0 
order by i;

-----------
Answer: 4613732

Josh Cheek • Jun 15 '18

My original solution (Ruby)

a, b, sum = 1, -1, 0
while a <= 4_000_000
  a, b = a+b, a 
  sum += a if a.even?
end
sum # => 4613732

I also thought it would be fun to try it as a lazy enumerator, though I still like my original solution better.

a, b = 1, -1
loop.lazy
    .map { a, b = a+b, a; a }
    .take_while { |n| n <= 4_000_000 }
    .select(&:even?)
    .sum # => 4613732

Oskar Larsson • Jun 14 '18

In Javascript using filter and reduce.

var memo = [0, 1];
function fib (n) {
    if(memo.length-1 < n) {
        memo[n] = fib(n-1)+fib(n-2);
    }
    return memo[n];
}

// creates array with elements from function that takes the index as argument while a given condition holds
function takeWhile (fromFunc, cond, arr=[]) {
    var n = arr.length;
    var val = fromFunc(n);
    if(cond(val)) {
        arr.push(val);
        return takeWhile(fromFunc, cond, arr);
    }
    return arr;
}

var sum = 
    takeWhile(fib, n => n < 4000000)
    .filter(n => n%2==0)
    .reduce((acc, c) => acc+c, 0);

console.log(sum);

Haskell:

fibo a b = a:fibo b (a+b)
isEven = (== 0) . flip mod 2

fibSumEvenUnder n = sum $ filter isEven $ takeWhile (<n) $ fibo 1 2
ans = fibSumEvenUnder 4000000

Jay • Jun 15 '18 • Edited

A simple iterative Rust Solution.
Takes about 0.9 sec, and optimized one takes 0.35 sec

fn fibo(mut a: i64, mut b: i64, max: i64) -> i64 {
    let mut sum = 0;
    while a < max {
        if a % 2 == 0 {
            sum += a;
        }
        let c = a+b;
        a = b;
        b = c;
    }
    sum
}

fn main() {
    println!("{}", fibo(1,2,4000000))  // 4613732
}

Priyansh Jain • Jun 15 '18 • Edited

def fibonacci(num, prev_num, sum=0):
    print(num, prev_num, sum)
    if num % 2 == 0:
        sum += num
    if num < 4000000:
        return fibonacci(num + prev_num, num, sum)
    return sum


print(fibonacci(1, 1))

Uses recursion, can someone explain how to calculate the complexity?

Seiei Miyagi • Jun 14 '18

Ruby✨💎✨

puts Enumerator.new { |y|
  f1, f2 = 0, 1
  f1, f2 = f1 + f2, f1 while y << f1
}.take_while {|x| x <= 4_000_000 }.select(&:even?).sum

Stephanie Handsteiner • Jun 13 '18 • Edited

Solved a few of the Euler challenges a few years ago (when I was still in high school, because what else would you do?) using PHP.

Solution: 4613732

$sum = 0; $curr = 2; $prev = 1; $goal = 4000000; while ($curr < $goal) { if($curr % 2 == 0) { $sum += $curr; } $tmp = $prev; $prev = $curr; $curr += $tmp; } echo $sum;

Abou Bakr G. • Jun 17 '18

I have just given it a try in Ruby

def fibonacci_numbers(upto)
  sequence = [0, 1]

  loop do
    next_number = sequence[-2] + sequence [-1]
    sequence.push next_number if next_number < upto
    break unless next_number < upto
  end

  sequence
end

def sum_of_even_numbers(upto)
  sequence = fibonacci_numbers(upto)

  sequence.select{ |el| el % 2 == 0 }.reduce(:+)
end

puts sum_of_even_numbers(4000000)

Kasey Speakman • Jun 13 '18 • Edited

Elm

Algorithm code

sumEven a sum =
  if a % 2 == 0 then
    a + sum
  else
    sum

sumfibs max a b sum =
  if a > max then
    sum
  else
    sumfibs max b (a + b) (sumEven a sum)

To call, max Fib value = 4000000, start with first 2 Fibs (1 and 2), initial sum = 0.

sumfibs 4000000 1 2 0

Pretty understandable, no?

Stephen Leyva (He/Him) • Jun 14 '18 • Edited

Recursive caching implementation

def solve(n):
    even_terms = []
    i = 2
    current = 0
    while current <= n:
        current = fib(i)
        even_terms.append(current)
        i += 3
    return sum(even_terms)


def fib(n, cache={1: 1, 2: 2}):
    if n not in cache:
        cache[n] = fib(n-1, cache) + fib(n-2, cache)
    return cache[n]

Ryan Palo • Jun 13 '18 • Edited

4,613,732! :D

"""Find the sum of even Fibonacci numbers less than 4,000,000"""

def fibonacci(cap):
    """Generates fibonacci numbers less than cap"""
    a, b, c = 0, 1, 1
    while c < cap:
        yield c
        a, b = b, c
        c = a + b

def even_fib_sum(cap):
    """Returns the sum of even fibonacci numbers less than cap"""
    return sum(fib for fib in fibonacci(cap) if fib % 2 == 0)

if __name__ == "__main__":
    print(even_fib_sum(4000000))
    print(list(fibonacci(4000000))

# => 4613732
# => [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578]

Dave Jacoby • Jun 13 '18 • Edited

I solved Euler 1-3 in 2015 but stopped...

#!/usr/bin/env perl
use feature qw{say state} ;
use bigint;
my $max = 4_000_000 ;

my $sum = 0 ;
while (1){
    state $i = 0;
    $i++;
    my $f = fibonacci($i);
    my $e = $f %2==0?1:0;
    last if $f > $max ;
    $sum += $f if $e;
    }
say $sum;

sub fibonacci {
    my $i = shift ;
    state $cache ;
    $cache->[0]=1;
    $cache->[1]=1;
    if ( $cache->[$i] ) { return $cache->[$i] }
    $cache->[$i] = $cache->[$i-1] + $cache->[$i-2] ;
    return $cache->[$i] ;
    }

Marat Tukhvatullin • Jun 21 '18 • Edited

Clojure 5-10ms

(def fib (lazy-cat [1 1] (map + (rest fib) fib)))
(defn euler2 [] (reduce + (filter even? (take-while (fn [x] (< x 4000000)) fib))))
(euler2)

Ademola John • Jan 6 '20 • Edited

Here was my solution in Javascript to the problem on Euler

Nwanze franklin • Jun 13 '18

Modified version of project Euler can be found here hackerrank.com/contests/projecteul...

its quite interesting

Hannah (she/her) • Jun 30 '18

It's cool to see all the different solutions here. I wrote a post that covers the Fibonacci sequence last month. 😃