22
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Does in range(1000) really mean 1...999 (remember the question asks for below 1000) \$\endgroup\$ – Gottfried Helms Sep 5 '15 at 13:20
14
\$\begingroup\$
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  
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – mkrieger1 Sep 3 '15 at 13:38
  • \$\begingroup\$ Is it more clear now ? \$\endgroup\$ – Heslacher Sep 3 '15 at 13:39
  • \$\begingroup\$ 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. \$\endgroup\$ – mkrieger1 Sep 3 '15 at 13:49
  • \$\begingroup\$ I don't do python, I just googled about range() and saw on could use the optional start parameter. I will rephrase my answer. \$\endgroup\$ – Heslacher Sep 3 '15 at 13:52
  • 1
    \$\begingroup\$ 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." \$\endgroup\$ – porglezomp Sep 3 '15 at 16:20
19
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • 7
    \$\begingroup\$ Instead of calling floor, you can use the integer division operator, //. Also, the relevant concept is the very useful to remember inclusion-exclusion principle. \$\endgroup\$ – Jaime Sep 3 '15 at 15:33
  • 7
    \$\begingroup\$ 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. \$\endgroup\$ – Peter Tirrell Sep 3 '15 at 20:19
10
\$\begingroup\$

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))))
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ @CoolGuy should work with pithon 2 too \$\endgroup\$ – Caridorc Sep 3 '15 at 15:34
  • \$\begingroup\$ Hmm. I thought that putting parentheses around the print will raise some error... \$\endgroup\$ – Spikatrix Sep 3 '15 at 15:39
  • 1
    \$\begingroup\$ @CoolGuy almost.. not using parens in python 3 for print is an error \$\endgroup\$ – Caridorc Sep 3 '15 at 15:53
  • \$\begingroup\$ @CoolGuy Unnecessary parens are fine in any version of Python, and they don't need any surrounding whitespace. \$\endgroup\$ – isaacg Sep 5 '15 at 0:04
8
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Be careful however, because xrange is bad advice for Python 3. \$\endgroup\$ – Nayuki Sep 4 '15 at 0:47
  • \$\begingroup\$ @Nayuki, a link to why it's bad advice would be helpful. \$\endgroup\$ – Wildcard Nov 18 '16 at 3:49
  • 1
    \$\begingroup\$ @Wildcard Python 3 doesn't have xrange, because range is already a generator. I presume that's what they were getting at. \$\endgroup\$ – SuperBiasedMan Nov 18 '16 at 9:49
8
\$\begingroup\$

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]))
| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ 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)) \$\endgroup\$ – yoniLavi Sep 3 '15 at 22:37
4
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.