11 Jan 09 Project Euler: Problem 2 in Ruby

My solution for Project Euler problem #2 came out a little fugly mainly because of the global variables, but it works. The "secret" to getting the program to run in a reasonable amount of time is to store the values of the fibonacci sequence as you compute them instead of processing the same data over again.

Problem #2

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

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

My Solution

max    = 4_000_000
total  = 0
$stack = []
 
def fib n
  if n == 0
    return 1
  end
  if n == 1
    return 2
  end
  return $stack[n - 1] + $stack[n - 2]
end
 
max.times do |i|
  $stack[i] = fib i
  if $stack[i] > max
    break
  end
  if $stack[i] & 1 == 0
    total += $stack[i]
  end
end
 
puts total

As is quickly becoming the case, Olathe's solution was much more elegant than mine:

x, y, sum = 1, 1, 0
while sum < 1_000_000
  sum += (x + y)
  x, y = x + 2*y, 2*x + 3*y
end
 
puts "Sum is #{ sum }."

Tags: project euler, ruby

Filed in code

Reader's Comments

1. Dan Kubb | 14 Mar 2009 12:15 am

   How I’ve been approaching Project Euler is I try to solve every problem at least twice: from the programmer’s point of view, and then from the mathemetician’s. I’m not a mathematician at all, but I’m using the project to self-teach myself concepts that I’d probably learned once and forgotten.

   Since I’m more of a programmer my first attempt at this problem was:

   sum = 0
   previous = 1
   current = 2

   while current <= 4_000_000
   sum += current if current.even? # Fixnum#even? available in Ruby 1.8.7
   previous, current = current, current + previous
   end

   Which is pretty much like Olathe’s approach (except you’ll note his code is for a slightly different question). The bad thing about this is that every 3rd time through the loop is when it actually adds to the sum (since every 3rd number in the fibonacci sequence is even).

   Some of the first few comments in that thread outline a mathematical approach that gives you an approximate answer which you round to get the right one.

   I did some digging and found out there’s a mathematical formula for this exact case already called Binet’s fomula (strangely enough no one mentions the formula name, but the’s a cryptic — to me — explanation on page 1 of the problem 2 thread). I wrote a solution for in Ruby using this formula:

   sq5 = Math.sqrt(5)
   phi = (1 + sq5) / 2.0

   sum = 0
   n = 3

   while sum <= 4_000_000
   sum += (phi ** n – (1 – phi) ** n) / sq5
   n += 3
   end

   sum = sum.to_i

   This loops the minimal number of times and scales much better than the first solution as the limit increases.

2. shah | 18 Oct 2009 12:06 pm

   1 1 2 3 5 8 13 21 plz solve the problem using for loop with java script.

3. me | 30 Dec 2009 11:47 pm

   @Dan
   I missed this comment somehow Dan, great info thanks very much!