DEV Community

Discussion on: Project Euler #2 - Even Fibonacci numbers

View post
Collapse
 
maxart2501 profile image
Massimo Artizzu • • 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.)

Collapse
 
nestedsoftware profile image
Nested Software • • 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.

Collapse
 
mortoray profile image
edA‑qa mort‑ora‑y •

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.

Thread Thread
 
maxart2501 profile image
Massimo Artizzu •

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!

Collapse
 
kepta profile image
Kushan Joshi • • 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

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

Now we can use the same logic to finder other n's:
4Fn = Fn+1 - Fn-1
4Fn-1 = Fn - Fn-2
4Fn-2 = Fn-1 - Fn-3
4Fn-3 = Fn-2 - Fn-3
...
...
4F4 = F5 - F3
4F3 = F4 - F2
4F2 = F3 - F1
4F1 = 4F1

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

4Fn = Fn+1 - Fn-1
4Fn-1 = Fn - Fn-2
4Fn-2 = Fn-1 - Fn-3
4Fn-3 = Fn-2 - Fn-3
...
...
4F4 = F5 - F3
4F3 = F4 - F2
4F2 = F3 - F1
4F1 = 4F1

4Fn + 4Fn-1 + 4Fn-2 + ... + 4F2 + 4F1 = Fn+1 + Fn - F2 + 3F1

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

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

Sn= ( Fn+1 + Fn - F2 + 3F1 ) / 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 Fn.

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
image
And if you compute the roots and follow along the url I posted above, you will end up with this
image

This gives us a function to compute Fn .

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

Collapse
 
maxart2501 profile image
Massimo Artizzu •

I applaud your solution, fellow math lover! 👏