Project Euler: Problem 2 in Ruby

Problem 2 in Project Euler is as follows:

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.

I had previously solved this in Groovy/Java. Here is my Ruby solution…

First, a simple algorithm to display the Fibonacci numbers up to ‘max’ would be:

  max = 4000000
  a = 0
  b = 1
  nextFib = 0
  puts a
  puts b
  begin
    nextFib = a + b
    puts nextFib
    a = b
    b = nextFib
  end while (nextFib < 4000000)

Next, the brute force solution to problem 2 of iterating of generating all the numbers, and only summing those that are divisible by 2:

  max = 4000000
  a = 0
  b = 1
  sum = 0
  begin
    nextFib = a + b
    if (nextFib % 2 == 0)
      sum += nextFib
    end
    a = b
    b = nextFib
  end while (nextFib < max)
  puts "Sum=#{sum}"

This ran in 0.000264s on my machine.

Next, the slightly more elegant solution based on the fact that in the Fibonacci series
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610
Only the 4th, 7th, 10th, 13th etc elements are even. That is, every 3rd element starting at the 4th.
This provides a more elegant solution, where we no longer need to check if a number is even:

  max = 4000000
  a = 1
  b = 1
  nextFib = a+b
  sum = 0
  while (nextFib < max)
    sum += nextFib
    a = nextFib + b
    b = a + nextFib
    nextFib = a+b
  end
  puts "Sum=#{sum}"

This ran in 0.000118s on my machine, about half the time of the previous solution.

Finally, the constant time solution. I did not figure this out myself first time around, but looking at the numbers that are actually even from the series:
2, 8, 34, 144, 610, 2584
There is an underlying formula, namely:
f(n) = 4f(n-1) + f(n-2)
for example 34 = 4(8) + 2
This leads to this solution:

  max = 4000000
  a = 2
  b = 8
  nextEvenFib = a+(4*b)
  sum = 0
  while (nextEvenFib < max)
    sum += nextEvenFib
    a = b
    b = nextEvenFib
    nextEvenFib = a+(4*b)
  end
  puts "Sum=#{sum}"

This runs in just 0.000101s on my machine.

Tags: euler, ruby