# Shaun Abram

Java and Technology weblog

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