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: euler, ruby