27
\$\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\$
1
  • \$\begingroup\$ Does in range(1000) really mean 1...999 (remember the question asks for below 1000) \$\endgroup\$ Sep 5, 2015 at 13:20

6 Answers 6

15
\$\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  
\$\endgroup\$
9
  • \$\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, 2015 at 13:38
  • \$\begingroup\$ Is it more clear now ? \$\endgroup\$
    – Heslacher
    Sep 3, 2015 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, 2015 at 13:49
  • 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, 2015 at 16:20
  • 1
    \$\begingroup\$ 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 ;) \$\endgroup\$
    – Shaz
    Sep 3, 2015 at 17:59
23
\$\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
\$\endgroup\$
2
  • 8
    \$\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, 2015 at 15:33
  • 9
    \$\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\$ Sep 3, 2015 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))))
\$\endgroup\$
4
  • \$\begingroup\$ @CoolGuy should work with pithon 2 too \$\endgroup\$
    – Caridorc
    Sep 3, 2015 at 15:34
  • \$\begingroup\$ Hmm. I thought that putting parentheses around the print will raise some error... \$\endgroup\$
    – Spikatrix
    Sep 3, 2015 at 15:39
  • 1
    \$\begingroup\$ @CoolGuy almost.. not using parens in python 3 for print is an error \$\endgroup\$
    – Caridorc
    Sep 3, 2015 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, 2015 at 0:04
9
\$\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]))
\$\endgroup\$
1
  • 3
    \$\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, 2015 at 22:37
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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Be careful however, because xrange is bad advice for Python 3. \$\endgroup\$
    – Nayuki
    Sep 4, 2015 at 0:47
  • \$\begingroup\$ @Nayuki, a link to why it's bad advice would be helpful. \$\endgroup\$
    – Wildcard
    Nov 18, 2016 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\$ Nov 18, 2016 at 9:49
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.

\$\endgroup\$
0

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