Project Euler 1:Find the sum of all the multiples of 3 or 5 below 1000

Question

I am trying to solve math problems with Ruby from the Project Euler. Here is the first one I tried:

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.

Please help me to improve my code.

total = 0

(0...1000).each do |i|
  total += i if (i%3 == 0 || i%5 == 0)
end

puts total

Answer 1

Much faster (constant time) answer:

def sum_multiples(multiple, to)
    n = (to-1) / multiple
    n * (n+1) / 2 * multiple
end

irb(main):001:0> sum_multiples(3, 10) + sum_multiples(5, 10) - sum_multiples(15, 10)
=> 23
irb(main):002:0> sum_multiples(3, 1000) + sum_multiples(5, 1000) - sum_multiples(15, 1000)
=> 233168

Why does this work? sum_multiples works out the sum of multiples of multiple up to but not including to (it relies on integer division). It first works out the number of number of multiples being summed (n), then multiples the standard formula for the sum of 1..n = n(n+1)/2 by multiple. Using this, we can add together the sums for the multiples of 3 and 5. We must then not forget that some numbers are multiples of both 3 and 5, so we subtract multiples of 15 (3*5).

Although your answer is more than fast enough for the constraints in this problem (it should run in about 1 millisecond on modern hardware), a faster solution such as the one I provide will give a result on very large numbers.

Answer 2

Well, first you can skip roughly 666 numbers by starting at 3, incrementing by 3. That way, you're only considering multiples of 3. Then do a second loop, starting from 5, incrementing by 5. Here, you need to check for multiples of 3 (or skip every 3rd generated number, as it just so happens that those will be multiples of 3), as they've been summed before.

This will have you check ~500 numbers, roughly half of the required numbers.

Alternatively, you can see if you can figure out a closed form for the sum (in principle, sum the numbers from 1 to floor(max,N), multiply this by N, do this for both your Ns (3 and 5), but then you'll have to subtract the double-counted numbers, but that's essentially subtracting the same for N=15).