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

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)

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

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)

## No comments:

Post a Comment