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]

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

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:

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:

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

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

constSQ5=5**.5;constPHI=(1+SQ5)/2;functionallEvenFibonacciUpTo(limit){consthighestIndexBelowLimit=Math.floor(Math.log(limit*SQ5)/Math.log(PHI));// I love expressive variable names, but the formula could get too long!constn=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! 🎉

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)

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_{4} = F_{5} - F_{3} 4F_{3} = F_{4} - F_{2} 4F_{2} = F_{3} - F_{1} 4F_{1} = 4F_{1}

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

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_{2} + 3F_{1} ) / 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

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.

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.

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

"""
Even Fibonacci numbers: Project Euler Problem 2
Solution in Python
https://projecteuler.net/problem=2
Takes 0.4s on my computer
"""deffibonacci_sequence(n):numbers=[0,1]whilenumbers[-1]<n:numbers.append(numbers[-1]+numbers[-2])returnnumbersdefsum_even_fibonacci_numbers(n):# O(N) Complexity
sequence=fibonacci_sequence(n)sequence=[nforninsequenceifn%2==0]returnsum(sequence)print(sum_even_fibonacci_numbers(4000000))

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.

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.

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

varmemo=[0,1];functionfib(n){if(memo.length-1<n){memo[n]=fib(n-1)+fib(n-2);}returnmemo[n];}// creates array with elements from function that takes the index as argument while a given condition holdsfunctiontakeWhile(fromFunc,cond,arr=[]){varn=arr.length;varval=fromFunc(n);if(cond(val)){arr.push(val);returntakeWhile(fromFunc,cond,arr);}returnarr;}varsum=takeWhile(fib,n=>n<4000000).filter(n=>n%2==0).reduce((acc,c)=>acc+c,0);console.log(sum);

"""Find the sum of even Fibonacci numbers less than 4,000,000"""deffibonacci(cap):"""Generates fibonacci numbers less than cap"""a,b,c=0,1,1whilec<cap:yieldca,b=b,cc=a+bdefeven_fib_sum(cap):"""Returns the sum of even fibonacci numbers less than cap"""returnsum(fibforfibinfibonacci(cap)iffib%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]

## Project Euler #2 - Even Fibonacci numbers

## Peter Kim Frank on June 13, 2018

Math to the rescue again!

To compute the

n-th Fibonacci number, you can use the Binet formula:where

φis the Golden Ratio, (1 + √5)/2. Also, it's given thatf(0) = 0 andf(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:In fact,

f(33) = 3524578 andf(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 everyf(3k) forkfrom 0 to 11. Using the known formula:and using

a=φ,h= 3 andn= 11, we have:So, more in general, using JavaScript (for example):

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

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_{4}= F_{5}- F_{3}4F_{3}= F_{4}- F_{2}4F_{2}= F_{3}- F_{1}4F_{1}= 4F_{1}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_{4}=~~F~~-_{5}~~F~~_{3}4F_{3}=~~F~~- F_{4}_{2}4F_{2}=~~F~~- F_{3}_{1}4F_{1}= 4F_{1}4F

_{n}+ 4F_{n-1}+ 4F_{n-2}+ ... + 4F_{2}+ 4F_{1}= F_{n+1}+ F_{n}- F_{2}+ 3F_{1}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:

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

I applaud your solution, fellow math lover! 👏

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.

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.

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!

OOhh Project Euler problems are my favorite!

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

The output was interesting!

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.

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.

My original solution (Ruby)

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

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 :)

In Javascript using filter and reduce.

Haskell:

Ruby✨💎✨

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

A simple iterative Rust Solution.

Takes about 0.9 sec, and optimized one takes 0.35 sec

Recursive caching implementation

## Elm

## Algorithm code

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

Pretty understandable, no?

I have just given it a try in Ruby

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;

Haskell:

Racket:

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

4,613,732! :D

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);`

Clojure 5-10ms

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

its quite interesting

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

/*Even Fibonacci numbers

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. */

## include

using namespace std;

int main()

{

int n1=1, n2=2 ,n3=0 , sumeven=0;

cout<<"the sum of the even-valued terms = "<<sumeven;

return 0;

}

C++ >> output>> 4613732