## Project Euler: Fibonacci Sequences

Bear Giles | February 5, 2011Project Euler (http://projecteuler.net/) is an interesting site for somebody who wants to develop their mathematical skills or keep them sharp. It’s really cool that (at the introductory level) there’s usually a brute force approach in a classic procedural language like Java, a cleaner brute force approach in a functional language, and a much cleaner solution if you use a bit of math. You can learn a lot by exploring the last approach.

There’s one problem though – there’s not enough information to know what to search for if you don’t already know what to search for. You can get that information in the comments from others once you solve the problem via brute force methods but that requires you to solve the problem via brute force solutions. That’s not always practical.

Google is another approach but the links often give you the answer without providing insight into how to get there. That’s great if you only want to answer the question, not so great if you want to learn a bit more math.

Some sites provide a bit more insight into the problem. I’ll try to add my own feeble contributions. There will be a brief insight above the break and a fuller discussion below the break. Unfortunately this won’t help much if you’re reading an RSS feed. Sorry.

The first issue is Fibonacci sequences. That is, slightly rephrased from the Project Euler definition, the sequence defined by:

- F(0) = 0
- F(1) = 1
- F(n) = F(n-1) + F(n-2) where n > 1

F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2) where n > 1

(The other common definition sets the first two values to 1 but the results are equivalent.)

So what insight do we have regarding the sum of even terms?…

Think back to elementary school math. We all learned a very simple rule:

- the sum of two even numbers is even.
- the sum of an even and odd number is odd.
- the sum of two odd numbers is even.

This means that a sequence of sums like the Fibonacci can have only two possible forms:

- all even numbers
- one even number, two odd numbers, one even number, repeat….

If follows that a sum of even Fibonacci terms will only need to consider every third value.

We can take this insight a bit further by making a slight change to the recursion rule. Starting with F(5) for reasons that will soon be obvious we have

- F(5) = F(4) + F(3)
- = (F(3) + F(2)) + F(3)
- = 2 F(3) + F(2)

F(5) = F(4) + F(3) = (F(3) + F(2)) + F(3) = 2 F(3) + F(2)

That doesn’t look like much of a gain but notice that F(2) and F(5) are in the same position relative to the even terms. (Remember F(0) = 0 so our even terms will be at multiples of 3.)

Let’s see what happens if we follow this pattern a little further….

- F(8) = 2 F(6) + F(2)
- = 2 F(6) + 2 F(3) + F(2)
- F(11) = 2 F(9) + F(8)
- = 2 F(9_ + 2 F(6) + F(2)

F(8) = 2 F(6) + F(2) = 2 F(6) + 2 F(3) + F(2) F(11) = 2 F(9) + F(8) = 2 F(9_ + 2 F(6) + F(2)

We can easily use induction to prove the general form

- F(3n+2) = 2 * sum(F(3i) for i=0..n) + F(2) for n > 0

F(3n+2) = 2 * sum(F(3i) for i=0..n) + F(2) for n > 0

Solving for the sum of even terms and recognizing that F(2) = 1 we have

- sum(F(3i) for i=0..n) = (F(3n+2) - 1)/2 for n > 0

sum(F(3i) for i=0..n) = (F(3n+2) - 1)/2 for n > 0

We don’t need to compute an explicit sum of Fibonacci terms, we can just find the appropriate term and solve for the sum of even terms!

Can we do better? Yes!

A sequence like the Fibonacci sequence has a ‘closed form’ solution. That is, we don’t need to compute all 2 billion terms to get F(2,000,000,000), we can just punch in a few numbers and get any desired term.

I won’t give that equation here – it’s easily found on Wikipedia – but from here the only difficulty is determining which value of F(n) is larger than the specified threshold.