# Project Euler #1: Multiples of 3 and 5

Challenge Description:

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

total_sum = 0
for i in range(1000):
if (i%3 == 0 or i%5 == 0):
total_sum = total_sum+i
print total_sum

• Does in range(1000) really mean 1...999 (remember the question asks for below 1000) Sep 5 '15 at 13:20

total_sum = 0
for i in range(1000):
if (i%3 == 0 or i%5 == 0):
total_sum = total_sum+i
print total_sum


You should leave your numbers, variables and operators some space to breathe by adding some horizontal space between them which improves readability a lot.

total_sum = 0
for i in range(1000):
if (i % 3 == 0 or i % 5 == 0):
total_sum = total_sum + i
print total_sum


As natural numbers aren't explictly defined containing 0 you could also use the two-parameter form of the range() function and specify the start parameter like so

total_sum = 0
for i in range(1, 1000):
if (i % 3 == 0 or i % 5 == 0):
total_sum = total_sum + i
print total_sum

• I'm not sure I understood your second point, and I'm less sure OP did. For example, you mention a start parameter, but the following code example doesn't contain this word. Maybe you could make more clear what you mean. Sep 3 '15 at 13:38
• Is it more clear now ? Sep 3 '15 at 13:39
• A bit. I guess what's throwing me off is that you've written "a start parameter", as if they were several "start parameters" and you could choose one of them; but you mean the first parameter of the range function, which is called "start". Ideally there would also be a link to the documentation so that one could immediately see the different forms of the function. Sep 3 '15 at 13:49
• Just a note, since the Natural numbers is very frequently defined to include 0, I don't think the last change is actually an improvement aside from a gain in "efficiency." Sep 3 '15 at 16:20
• There's also this, where they say they'll explicitly state which set they're working with. However, for this problem it doesn't matter since 0 is never a multiple of 3 or 5. In fact, you could start your range at 3 and call it good based on the same premise - and then we don't have to quibble over how wrong you are to exclude 0 from the natural numbers ;)
– Shaz
Sep 3 '15 at 17:59

You don't need iteration at all for this problem.

Consider; the sum of all numbers from 1 to n is equal to n*(n+1)/2. Also the sum of all numbers less than n that divides d equals d times the sum of all numbers less than n/d.

So the sum of all numbers less than 1000 that divides 3 is

3*floor(999/3)*(floor(999/3)+1)/2


Likewise the sum of all numbers less than 1000 that divides 5 is

5*floor(999/5)*(floor(999/5)+1)/2


Adding the two numbers would overcount though. Since the numbers that divides both 3 and 5 would get counted twice. The numbers that divides both 3 and 5 is precisely the numbers that divides 3*5/gcd(3,5)=15/1=15.

The sum of all numbers less than 1000 that divides 15 is

15*floor(999/15)*(floor(999/15)+1)/2


So the final result is that the sum of all numbers less than 1000 that divides either 3 or 5 equals:

  3 * (floor(999/3)  *  (floor(999/3)+1))/2
+ 5 * (floor(999/5)  *  (floor(999/5)+1))/2
-15 * (floor(999/15) * (floor(999/15)+1))/2

• Instead of calling floor, you can use the integer division operator, //. Also, the relevant concept is the very useful to remember inclusion-exclusion principle. Sep 3 '15 at 15:33
• I've learned that this is the trick for most (all?) of the Project Euler problems I've worked on. They usually have a fairly obvious brute force solution and then a straightforward "more obscure" solution based on a math algorithm. Sep 3 '15 at 20:19

Define a function to solve more general problems:

def divisible_by_under(limit, divs):
return (i for i in  range(limit) if any(i % div == 0 for div in divs))


This works for any limit and any divisor and is inside an easy to test function.

print(sum(divisible_by_under(1000, (3, 5))))

• @CoolGuy should work with pithon 2 too Sep 3 '15 at 15:34
• Hmm. I thought that putting parentheses around the print will raise some error... Sep 3 '15 at 15:39
• @CoolGuy almost.. not using parens in python 3 for print is an error Sep 3 '15 at 15:53
• @CoolGuy Unnecessary parens are fine in any version of Python, and they don't need any surrounding whitespace. Sep 5 '15 at 0:04

You could use list comprehension, to save a few lines, but it does exactly the same as yours:

print(sum([i for i in range(1000) if i%3==0 or i%5==0]))

• I love this form best, and just wanted to add that the sum function takes a generator expression as well, so you don't need the square brackets: print(sum(i for i in range(1000) if i%3==0 or i%5==0)) Sep 3 '15 at 22:37

You don't need to type this out fully:

total_sum = total_sum+i


Python has a += operator, basically shorthand for what you have above. Take what's on the left of the operator and add the result of what's on the right.

total_sum += i


Also when in Python2.7 it's recommended you use for i in xrange(1000). range will immediately create a full list of numbers it stores in memory, while xrange is a generator that produces each number as it's needed. The performance difference is helpful for large ranges but it's generally a good habit to keep.

• Be careful however, because xrange is bad advice for Python 3. Sep 4 '15 at 0:47
• @Wildcard Python 3 doesn't have xrange, because range is already a generator. I presume that's what they were getting at. Nov 18 '16 at 9:49

This code is extremely inefficient. Using some basic math we can reduce runtime to constant time complexity. For any n (in this case 1000), we can predict the number of numbers < n and divisible by 3 or 5:

• numbers divisible by 3: lowerbound(n / 3)
• numbers divisible by 5: lowerbound(n / 5)

The sum of all numbers divisible by 3 or 5 can then be predicted using eulers formula:
the sum of all numbers from 1 to n is n(n + 1)/2. Thus the sum of all numbers n divisible by 3 is:

int div_3 = (n / 3)
int sum_div_3 = div_3 * (div_3 + 1) / 2 * 3


Now there's only one point left: all numbers that are divisible by 3 and 5 appear twice in the sum (in the sum of all numbers divisible by 3 and the sum of all numbers divisble by 5). Since 3 and 5 are prim, all numbers that are divisible by 3 and 5 are multiples of 15.

int sum_div3_5(int n)
int div_3 = (n - 1) / 3 ,
div_5 = (n - 1) / 5 ,
div_15 = (n - 1) / 15

int sum = div_3 * (div_3 + 1) * 3 / 2 + //sum of all numbers divisible by 3
div_5 * (div_5 + 1) * 5 / 2 - //sum of all numbers divisible by 5
div_15 * (div_15 + 1) * 15 / 2

return sum


I can't provide python code though.