Project Euler: Problem 2

Problem 2

JS Solution 1

JS Solution 2

I am awful at writing math proofs. But I happen to know that every 3rd fibonacci is even. Which means we could eliminate the modulo check.

In words, my understanding is:

• the sum of 2 odd numbers is always even
• the sum of an even and odd number is always odd
• the fibonacci sequence creates 2x as many odd numbers as it does even, because every even number is summed with an odd number (the numbers before, and after it in the sequence)

$fn0 = 1, fn1=1, fn2=2$ - Two odds sum to an even

$fn0 = 1, fn1=2, fn2=3$ - An odd and an even sum to an odd

$fn0 = 2, fn1=3, fn2=5$ - An odd and an even sum to an odd

$fn0 = 3, fn1=5, fn2=8$ - Two odds sum to an even

You can see how this odd-odd-even pattern repeats.

Let's modify the program to skip numbers. This requires an extra var but we skip the modulo check.

Conclusion

It's hard to see the speedup on this one, since the fibonacci sequence tends towards an out of bounds number before performance becomes an issue. But in theory the second solution is faster.

Final answer

$4,613,732$