Where did my proper divisor sum program went wrong?

When you do x=y=z=[], you're making x, y and z point to the same list. Example:

x=y=z=[]
# add element to x
x.append(1)
# add element to y
y.append(2)
# but x, y and z all point to the same list
print(z) # [1, 2]

So the first thing to fix is this, set a different list to each:

x = []
y = []
z = []

And now, when you add elements to one, it doesn't change the others.

Now the algorithm: in the first loop, c is the number you want to check. So in the second loop, the upper bound should be related to c, not to a.

Actually, to be honest, this code is too confusing to me and I gave up trying to understand what you did. So I'll just suggest another algorithm. And it seems that you were trying to code-golf, but for the sake of clarity, I'll use better names for the variables and not focus on the make-the-smallest-possible-code aspect.

First of all, you don't need to test number 1. One might think I'm "cheating", but 1 has no proper divisors, so the sum of their proper divisors is zero, hence it can already start at the deficients list.

And all numbers are divisible by 1, so the sum of divisors can be initialized with 1, and I can start checking the divisors from number 2.

To check if a number is divisible by another, just use the % operator, which gives you the remainder. Ex: when 100 is divided by 2, the remainder is zero (100 % 2 == 0), but by 3, the remainder is 1 (100 % 3 == 1). Hence, 2 is a divisor of 100, but 3 isn't. Tl;dr: just check if the result of % is zero.

Another important detail is: when you find a divisor, you potencially found another one. Let's say the number is 100. If I find divisor 2, I also found another divisor, which is the result of 100 divided by 2 (aka 50). The only exception is divisor 10, because 100 / 10 is also 10.

So, for each divisor found (the remainder is zero), I check if the other divisor is the same number (if not, I found another divisor). Using this method, I can iterate only until the square root of the number (ex: if the number is 100, I can make the loop until 10). That's because if some number N has divisors, it can be written as a product of two integers (let's say a * b), which means that if a and b were both greater than the square root of N, then their product would be greater than N, so at least one of them must be smaller than the square root. Therefore, if we loop until the square root, we find one divisor, and by dividing the number by this divisor, we find the other one.

The code will be like this:

from math import sqrt

x = int(input())

deficient = [ 1 ] # "cheating"
perfect = []
abundant = []
for n in range(2, x + 1): # no need to check 1
    # calculate sum of proper divisors of n
    div_sum = 1 # 1 is always a divisor
    for div_candidate in range(2, int(sqrt(n)) + 1):
        if n % div_candidate == 0: # divisor found
            div_sum += div_candidate
            # get the other divisor
            other_divisor = n // div_candidate
            if other_divisor != div_candidate: # avoid the square root, if n is a perfect square
                div_sum += other_divisor

    # add n to the proper list
    if div_sum > n:
        abundant.append(n)
    elif div_sum < n:
        deficient.append(n)
    else:
        perfect.append(n)

print([ abundant, perfect, deficient ])

Note that, in Python, when you print a list, it's already displayed delimited by [ ] and the elements separated by commas. So there's no need to make all those loops. Even if you need different separators, you could use join instead:

# just an example
numbers = [1, 2, 3]
# using join to print the numbers separated by some string
print('<{}>'.format('; '.join(map(str, numbers)))) # <1; 2; 3>
# in Python >= 3.6, use f-strings
print(f'<{"; ".join(map(str, numbers))}>') # <1; 2; 3>

Anyway, that's beside the point. If you print the lists directly, the output will be like [ element1, element2, etc ]. In the end, I put all the 3 lists inside another list, to make the ouput match the format specified by the challenge. Example, for x equals to 15, the output is:

[[12], [6], [1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15]]

Well, if you think that starting the deficients list with 1 is "cheating", then let's see another approach (still ignoring the code-golf aspect). You could create a generator function that yields the proper divisors, just to keep things more organized, IMO:

from math import sqrt

# generator function that yields all the proper divisors of n
def proper_divisors(n):
    if n <= 1: # for n <= 1, there are no proper divisors
        return
    yield 1 # 1 is always a divisor
    for div_candidate in range(2, int(sqrt(n)) + 1):
        if n % div_candidate == 0: # divisor found
            yield div_candidate
            # get the other divisor
            other_divisor = n // div_candidate
            if other_divisor != div_candidate:
                yield other_divisor

And then we can use this function with the built-in sum, to get the sum of those divisors:

x = int(input())
deficient = []
perfect = []
abundant = []

for n in range(1, x + 1):
    # calculate sum of proper divisors of n
    div_sum = sum(proper_divisors(n))

    # add n to the proper list
    if div_sum > n:
        abundant.append(n)
    elif div_sum < n:
        deficient.append(n)
    else:
        perfect.append(n)

print([ abundant, perfect, deficient ])

Of course you could also do it without the function, adding the if n <= 1 to the first code. But I don't really mind "cheating" and initializing the deficients list with 1.

If you want to code-golf, I'm not the best one to give you some advice (I can only suggest the more obvious thing). I think code golf is a curious thing, but I personally don't enjoy programming like that, because it starts getting too complicated, IMO. One example is this trick to have just one list of lists:

result = [ [], [], [] ]
for n in range(1, x + 1):
    # calculate sum of divisors of n
    div_sum = sum(proper_divisors(n))

    # add n to the proper list
    result[(n > div_sum) - (n < div_sum) + 1].append(n)

print(result)

It uses the suggested implementation of the cmp built-in, which no longer exists in Python. It basically returns -1 if n is less than div_sum, zero if they're equal and 1 if n is greater. Then I add 1 to this result, in order to get the respective index on the result list (which has 3 other lists in it: the abundant, perfect and deficient lists).

That's a way to make the code shorter, but certainly not clearer. Anyway, at least now you have a code that works and can code-golf it...

posted over 3 years ago

CC BY-SA 4.0

3y ago

hkotsubo‭

5110 reputation 20 69 575 229