CODEWITHSUNDEEP
pythongenerator
Yunti
Yunti

Reputation: 7448

Python generators and sum of multiples

For the below question: "Return the sum of the multiples of 3 and 5 below a number."

I tried to use:

def solution(number):
  return sum(x for x in range(1,number) if x%3==0 or x%5==0)

However this gives an overflow if the number is too large. I'm not clear how as I tried to use a generator expression (I'm new to these). I thought it was evaluating each x in the range at a time (without building the list) and only keeping the running tally of sum and not building a list before evaluating each item in the list. Can anyone explain why this doesn't work? Thanks.

Upvotes: 0

Views: 3820

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476709

Actually, that's not really an issue. An example with the python3 linux shell:

>>> def solution(number):
...   return sum(x for x in range(10**15,number) if x%3==0 or x%5==0)
... 
>>> solution(10**15+20)
9000000000000082
>>> solution(10**15+17)
8000000000000065

(used 20**15 as offset to speed things up) don't seem to result in 32-bit integer overflows.

Since the sum of all 32-bit integers can be represented by a 64-bit integer and you want to sum up multiples up to a 32-bit int, there is no problem with this.

It is possible one runs in memory overflow in python2 simply because the list is generated before the sum actually takes place. and there is no way to represent billions of numbers in reasonable memory.

But the way this is handled is simply not the was to tackle this. The sum is simply equal to:

n//15-1
---
\                               15 (m+1) (7*m+8)
/     7*15*i+3+5+6+9+10+12+15 = ---------------- where m=n//15-1
---                                     2
i=0

and you need to take the last numbers into account as well.

So a method to calculate this is:

def sol15floor(n) :
    m = (n-1)//15-1
    s0 = 15*(m+1)*(7*m+8)//2
    return s0 + sum(x for x in range(15*m+16,n) if x%3==0 or x%5==0)

Upvotes: 1

Related Questions