28
\$\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\$ Commented Sep 5, 2015 at 13:20

6 Answers 6

Reset to default
16
\$\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\$ Commented Sep 3, 2015 at 13:38
  • \$\begingroup\$ Is it more clear now ? \$\endgroup\$ Commented 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\$ Commented 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\$ Commented 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\$ Commented Sep 3, 2015 at 17:59
24
\$\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\$ Commented 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\$ Commented Sep 3, 2015 at 20:19
11
\$\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\$ Commented Sep 3, 2015 at 15:34
  • \$\begingroup\$ Hmm. I thought that putting parentheses around the print will raise some error... \$\endgroup\$ Commented Sep 3, 2015 at 15:39
  • 1
    \$\begingroup\$ @CoolGuy almost.. not using parens in python 3 for print is an error \$\endgroup\$ Commented 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\$ Commented Sep 5, 2015 at 0:04
10
\$\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\$ Commented Sep 3, 2015 at 22:37
9
\$\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\$ Commented Sep 4, 2015 at 0:47
  • \$\begingroup\$ @Nayuki, a link to why it's bad advice would be helpful. \$\endgroup\$ Commented 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\$ Commented Nov 18, 2016 at 9:49
5
\$\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

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.