Project Euler–Problem 2

Description

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

Solution

The solution to this problem again has a trivial solution and a slight optimization. The trivial solution simply involves creating a method to calculate the Fibonacci sequence up to 4 million and a second method to add the even terms together.

class Problem002
 include Enumerable

 def each
  last = 1; current = 2
  yield last; yield current
  while true
   last, current = current, last + current
   yield current
  end
 end

 def sum_to(maximum)
  take_while { |n| n < maximum }.select { |n| n.even? }.inject { |sum,n| sum + n}
 end
end

Problem002.new.sum_to(4_000_000)

Notice that here I’ve used a mix-in to make the problem itself an enumerable collection of Fibonacci terms. However, we have a slight optimization we can make by observing two things.
First is that we don’t actually need to yield all of the terms of the Fibonacci sequence, only the even terms. Notice that the only way to get an even term is if the previous two terms are both even or both odd. If we start with 1 and 2 our next term will be odd because an odd plus an even is odd. The next term will be odd as well because we now have an even followed by an odd. The third term will be even since an odd plus an odd is even. For the fourth term we are back to an odd followed by an even. So we see that if we start with the second term (2), we only need to yield every third term in the sequence^.
Our second observation is regarding calculating the terms themselves. we can see that each term is specified by the previous two terms in the sequence:

n = (n-1) + (n-2)
n-1 = (n-2) + (n-3)

However, this means that we can also express each term by any previous two terms in the sequence. Reversing this, it means we can specify any future term by the current two terms. So we can come up with the following:

Given n and m (the term before n)
n+1 = n + m
n+2 = (n+1) + n = (n + m) + n = 2n + m
n+3 = (n+2) + (n+1) = (2n + m) + (n + m) = 3n + 2m

As you can see, term n+1 doesn’t ever need to be computed since we can express n+2 and n+3 in terms of n and m.  This saves us computed 1/3 of all the values.  So our new more optimal solution looks like this:

class Problem002
 include Enumerable

 def each
  current = 2
  last = 1
  while true
   yield current
   last, current = 2*current + last, 3*current + 2*last
  end
 end

 def sum_to(maximum)
  take_while { |n| n < maximum }.inject { |sum,n| sum + n }
 end
end
Problem002.new.sum_to(4_000_000)

As always, the source is available on github, both the full source and specifications. Next time, finding the largest prime factor of a composite number.