Project Euler #2 - Even Fibonacci numbers

I had a blast reading through the many creative and varied approaches to solving Problem #1. There's something very fun and enlightening about seeing the same problem solved in different ways:

Project Euler #1 - Multiples of 3 and 5

Peter Kim Frank ・ Jun 11 '18

#projecteuler #challenge

Not sure if this will become a regular thing, but I wanted to keep this rolling and present Problem #2. Again, this is from the wonderful Project Euler.

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.

Look forward to seeing solutions in your language of choice!

Comments

[Ademola John]

Here was my solution in Javascript to the problem on Euler

function fiboEvenSum(n) { let previous = 0, current = 1, result = 0; for(let i = 0;i const next = previous + current; if(next % 2 ===0){ result += next; } if(next>n)break; previous = current; current = next; } return result; } fiboEvenSum(10);

[Hannah (she/her)]

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

[Marat Tukhvatullin]

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)

[Abou Bakr G.]

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)

[Jay]

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
}

[Ross Henderson]

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

[Priyansh Jain]

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?

[Josh Cheek]

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]

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