Multiples of 3 and 5 from Euler code challenge

I have implemented the first coding challenge on http://projecteuler.net/. I would love to get it reviewed by some expert rubyists!

# Multiples of 3 and 5
#
# If we list all of the natural numbers below 10 that are multiples of
# 3 and 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.

class Multiples

def multiples
numbers = Array(1..999)
multiples = Array.new
for i in numbers
if i%3 == 0 or i%5 == 0
multiples.push(i)
end
end
multiples
end

def sumMultiples(multiples)
total = 0
multiples.each { |i| total+= i }
puts(total)
end

end

multiples = Multiples.new
multiples.sumMultiples(multiples.multiples)


• Don't use or. It's for flow control. Use || for boolean logic.

• Don't use Array.new, use []

• Don't use (1..999).to_a or Array(1..999) when all you really want to do is iterate. It's expensive to instantiate a 1000 item array when really you just want to iterate from 1 to 999

• Any time you find yourself declaring an empty array and pushing items onto it in a loop, you are probably missing a map or select:

def multiples
numbers = Array(1..999)
multiples = Array.new
for i in numbers
if i%3 == 0 or i%5 == 0
multiples.push(i)
end
end
multiples
end


Could be better written this way:

def multiples
(1..999).select do |i|
i % 3 == 0 || i % 5 == 0
end
end


Your summation loop follows a similar pattern:

def sumMultiples(multiples)
total = 0
multiples.each { |i| total+= i }
puts(total)
end


Again, there is a more idiomatic way of doing this via inject:

def sumMultiples(multiples)
total = multiples.inject(&:+)
end


A breakdown of how this works can be found in How to sum array of numbers in Ruby?.

• thanks @meagar. That looks a lot more elegant. Also, thanks for the advice on not using Array(1..999). May 25, 2013 at 7:53

A fun question! A little mathematical analysis can go a long way in reducing the amount of computation:

First of all, you don't actually need to iterate anything. To get the sum of all the numbers from 1 to n, just get the midpoint between the first and last numbers, which is simply the arithmetic average (1+n)/2. Then multiply this average by n. So the sum of all the numbers from 1 to n is:

((1+n)/2) * n


Similarly, the sum of all the multiples of a from a to z (assuming z is a multiple of a) is the midpoint between a and z times the number of multiples of a in the sequence a .. z.

So, since there are 333 numbers in the sequence 3,6,9,12 ... 999, the sum of all the multiples of 3 that are less than 1000 is:

((3+999)/2) * 333


or, in other words 333 x 501.

And the sum of all the multiples of 5 that are less than 1000 would be:

((5+995)/2) * 199


which is 199 x 500.

If we added these two sums together, we would be almost done, except for one little detail: each number that is a multiple of 15 was added twice. So we have to subtract those.

The sum of all the multiples of 15 that are less than 1000 is ((15+990)/2) * 66, or 66 x 502.5.

((3+999)/2) * 333 + ((5+995)/2) * 199 - ((15+990)/2) * 66


which is

166,833 + 99,500 - 33,165


or 233,168.

A "technically correct, but totally useless" answer to the code challenge would be

def get_the_sum
233168
end


or without the syntactic shortcuts

def get_the_sum
sum = 233168
return sum
end


We can, however, write a more useful general purpose method

sum_all_multiples_ab(a,b,max)


that finds the sum of all multiples of a or b that are less than max. Then the answer to your example problem would be given by:

sum_all_multiples_ab(3, 5, 1000)


We could define such a method like this:

def sum_all_multiples_ab(a, b, max)
sum = sum_all_multiples(a, max)
sum += sum_all_multiples(b, max)
sum -= sum_all_multiples(a*b, max)
sum
end


where sum_all_multiples() is defined by

def sum_all_multiples(n,max)
count = (max-1)/n
last = count * n
sum = ((n + last) / 2.0) * count
sum
end


We need to specify 2.0 in the last computation because we want a real number result, whereas for count (the number of values) and last (the last multiple less than 1000 or max) we want the truncated integer result.

(We will only get an odd number for the average when we have an even number of values, so the ultimate result will always be an integer.)

• I made an edit to change the divisor in the last computation to 2.0 because we need a real, not integer (truncated) result. The other division statement, (max -1)/n, still needs a truncated result, however. May 25, 2013 at 13:46
  def sumMultiples(multiples)
# (...)
end


I wouldn't use camelCase here.

In Ruby there is a very solid convention:

• CamelCase for classes and modules
• CAPITALIZED_UNDERSCORED for constants
• snake_case for everything else (methods, variables)