Shaun Abram
Technology and Leadership Blog
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.