## Project Euler: Problem 1 in Ruby

In the process of trying to enhance my Ruby Skills, I am revisiting some of the Project Euler problems. I previously did problem 1 in Groovy/Java. Here is my Ruby solution.

First, a recap:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

My brute force solution.

``````
t = Time.now
n = 1000
sum = 0
for i in 1..n-1
if ((i%3==0) || (i%5==0))
sum = sum + i
end
end
puts sum
puts Time.now-t
``````

On my aging Macbook Pro, this took 0.000263 secs, well below the 1 second limit.

Next a slightly more elegant solution.

``````
t = Time.now
n = 1000
sum = 0
results = Set.new

for i in (3..n-1).step 3
results.add i
end
for i in (5..n-1).step 5
results.add i
end
results.each { |x| sum = sum + x }
puts sum
puts Time.now-t
``````

Surprisingly, this actually takes longer, at 0.000442 secs. I guess the Set operations and subsequent iteration are slow in Ruby.

The final solution (which I never remember, but is pretty neat) is based on 2 tricks.
1) The first is that what we are looking for, i.e. the sum all numbers up to 1000 divisible by 3, can be written as
3+6+9+ … +999
= 3*(1+2+3+…+1000/3)
Or more generally, where N is the max (in our case 1000) and n is the number it must be divisible by
= n(1+2+…N/n)
2) The second is that
1+2+3…+i
= (i/2)*(i+1)
= i*(i+1)/2

So the final solution can be boiled down to
n*i*(i+1)/2
where
N is the max (in our case 1000)
and n is the number it must be divisible by
and i is N/n rounded down

This all results in a constant time solution:

``````
\$max = 999
def euler1
t = Time.now
puts (sum(3) + sum(5)) - sum(15)
puts Time.now-t
end

def sums(divisor)
i = \$max / divisor
divisor*(i*(i+1)) / 2
end
``````

Which produces the correct result of 233168 in just 0.000041 seconds.

Tags: ,