CODEWITHSUNDEEP
pythonmath
Tetramputechture
Tetramputechture

Reputation: 2921

Looking for values in Python Dictionaries

I'm trying to memoize divisor sums of numbers.

divisorSums = {}

def sumDivisors(num):

    global divisorSums

    total = 0

    if num == 1:
        return 0

    for i in xrange(num/2, 0, -1):
        if i in divisorSums:
            return divisorSums[i]
        else:
            if not num % i:
                total += i

    divisorSums[num] = total

    return total

However, this returns 1 for all numbers, when I loop through the numbers. It is correct when it used singularly, so the problem is my lookup system. I'm pretty sure I don't understand how to look for a value in a dictionary. Can someone help me out?

Upvotes: 1

Views: 88

Answers (2)

perreal
perreal

Reputation: 98078

Here:

if i in divisorSums:
            return divisorSums[i]

returning divisorSums[i] is not the right thing to do as there may be some prime factors less than i. Here is one way using a helper function to remember/calculate factors of numbers: 

from itertools import groupby
divisorC={}
def divisors(num):
    if num in divisorC:
        return divisorC[num]
    l = {1:1}
    for i in xrange(num/2, 1, -1):
        if num % i == 0:
            l[i] = 1 
            l.update(divisors(i))
            l.update(divisors(num/i))
            break
    divisorC[num] = l 
    return divisorC[num]
def sumDivisors(num):
    if num == 1: return 0
    l = {}
    for i in xrange(num/2, 0, -1):
        if num % i == 0:
            l.update(divisors(i))
            l.update(divisors(num/i))
            l[i] = 1 
            l[num/i] = 1 
            break
    return sum(v for v in l)

Upvotes: 2

John La Rooy
John La Rooy

Reputation: 304355

The usual shortcut trick for memoize is to use a mutuable default argument

def sumDivisors(num, divisorSums={}):

    if num in divisorSums:          # Check if you have
        return divisorSums[num]     # memoized the answer here

    total = 0

    if num == 1:
        return 0

    for i in xrange(num/2, 0, -1):
        if not num % i:
            total += i

    divisorSums[num] = total

    return total

Other than that your code seems to work ok. How were you runnning it to get just 1?

Upvotes: 3

Related Questions