Reputation: 1287

Integer Overflow in Summing Multiples of 3 and 5

I am sure this question has been ask a lot, but I have checked other forums and have tried addressing the issue, which doesn't seem to help. I am thinking there is an overflow problem, but I can't remember on how to fix it. I took a long break from coding (my fault there) so I am trying some problems to help get me back in the swing of things. So, just wondering as to what is going wrong. When I try n = 1000 the answer is wrong but numbers smaller than that seem to work out right. Since large numbers won't work I think it's an integer overflow.

def n_number():
    n = raw_input("Enter a max number: ")
    try:
        int(n)
        return n

    except ValueError:
        print 'Value is not an integer'
        exit(1)

# 'function that will add multiples of 3 and 5 that are less than the given value, n.'
def sum_multiplies(n):
    sum = long(0)
    counter3, counter5 = int(1),int(1)

    value3 = 3*counter3
    value5 = 5*counter5

    while True:
        # 'sums of multiples of 5\'s less than n'
        if value5<int(n):
            sum+= value5
            counter5+=1
            value5 = 5*counter5

        # 'sums of multiples of 3\'s less than n'
        if value3<int(n):
            sum+= value3
            counter3+=1
            value3 = 3*counter3

        else:
            break

    print "sum: %s" %sum
    print "counter3: %s" %counter3
    print "counter5: %s" %counter5

def main():
    'max number is in n'
    n = n_number()

    sum_multiplies(n)

if __name__ == "__main__":
    main()

Upvotes: 0

Answers (5)

gsk

Reputation: 578

Using generators expressions, here's a one-liner

result = sum(num for num in xrange(1000) if (num % 5 ==0) or (num % 3 == 0))

Upvotes: 1

user1277476

Reputation: 2909

It should be pretty fast, pretty readable, and run on CPython 2.x and 3.x. I've #!'d it to pypy, but that's not out of necessity. Note that range() is eager on 2.x, lazy on 3.x:

#!/usr/local/pypy-1.9/bin/pypy

divisible_by_3 = set(range(0, 1000, 3))
divisible_by_5 = set(range(0, 1000, 5))

divisible_by_either = divisible_by_3 | divisible_by_5

print(sum(divisible_by_either))

Upvotes: 1

corsiKa

Reputation: 82589

You're currently doing this in O(n) time - you can do it in constant time!

' sum values from 1 to m'
def unitSum(m):
    return (m * (m + 1)) / 2

def sum_multiplies(n):
    threes = int(n / 3)
    fives = int(n / 5)
    fifteens = int(n / 15)
    threesum = unitSum(threes) * 3
    fivesum = unitSum(fives) * 5
    fifteensum = unitSum(fifteens) * 15
    return threesum + fivesum - fifteensum

You'll have to forgive my lack of python knowledge, I'm a java guy. There might be some casual syntax errors. But the idea here is that, for the example of n = 40, you're adding up 3 5 6 9 10 12 15 18 20 21 24 25 27 30 33 35 36 39 40. This is the same as 3 6 9 12 15 18 21 24 27 30 33 36 39 UNION 5 10 15 20 25 30 35 40 Now recognizing that 3 6 9 12 ... is the same as 3 * (1 2 3 4...), and the same with the fives, we can take the "unit sum" (1 2 3 4) up to the number of terms, which is n / mult, and multiply that sum by the mult, as we do with 3 * (1 2 3 4). The good news is the unit sum can be computed in constant time, as n * (n + 1) The only catch is that the ones that are a mult of 15 will be in there twice (counted in both the 5s and the 3s) so we have to subtract them out as well.

Upvotes: 2