# 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

I want to receive advice on my code.

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) – Gottfried Helms Sep 5 '15 at 13:20

## 6 Answers

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. – mkrieger1 Sep 3 '15 at 13:38
• Is it more clear now ? – Heslacher 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. – mkrieger1 Sep 3 '15 at 13:49
• I don't do python, I just googled about range() and saw on could use the optional start parameter. I will rephrase my answer. – Heslacher Sep 3 '15 at 13:52
• 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." – porglezomp Sep 3 '15 at 16:20

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. – Jaime 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. – Peter Tirrell 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 – Caridorc Sep 3 '15 at 15:34
• Hmm. I thought that putting parentheses around the print will raise some error... – Spikatrix Sep 3 '15 at 15:39
• @CoolGuy almost.. not using parens in python 3 for print is an error – Caridorc Sep 3 '15 at 15:53
• @CoolGuy Unnecessary parens are fine in any version of Python, and they don't need any surrounding whitespace. – isaacg Sep 5 '15 at 0:04

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. – Nayuki Sep 4 '15 at 0:47
• @Nayuki, a link to why it's bad advice would be helpful. – Wildcard Nov 18 '16 at 3:49
• @Wildcard Python 3 doesn't have xrange, because range is already a generator. I presume that's what they were getting at. – SuperBiasedMan Nov 18 '16 at 9:49

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)) – yoniLavi Sep 3 '15 at 22:37

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.

## protected by Community♦Jun 5 '16 at 6:09

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?