Odd divisor summation

Question

Given an integer, k, we define its odd divisor sum to be the sum of all k's odd divisors. For example, if k = 20, then the odd divisor sum would be 1 + 5 = 6. Similarly, if given an array of values, we can find the odd divisor sum of the array by summing the odd divisor sums for each element in the array.

For example, if array K = [3, 4, 20], the odd divisor sum of the array would be oddDivisorSum(3) + oddDivisorSum(4) + oddDivisorSum(20) = (1 + 3) + (1) + (1 + 5) = 11.

This code works, but it does not pass all the cases due to time. I wanted to see if there was a more efficient way to write this. I heard that memoization could work, but I am not sure show how to implement it.

numbers = [3,21,11,7]

def  count(numbers):
    total = 0
    for k in numbers:
        for i in range(1,k+1,2):
            if k % i == 0:
                total+=i
    return total

Answer 1

First I would suggest to separate the code into two functions: One which computes the sum of odd divisors of a single number, and another which adds the odd divisors of all numbers in a list. Also, use better function names, and add at least a simple doc comment:

def oddDivisorSum(n):
    """Return the sum of odd divisors of n."""
    # ... to do ...


def totalOddDivisorSum(numbers):
    """Return the sum of all odd divisors of all numbers."""
    return sum(oddDivisorSum(n) for n in numbers)

This makes the code more clear, better reusable, and makes it easier to add test cases.

To make the computation faster, two observations help:

1. If \$k\$ is a divisor of \$n\$, then \$\frac{n}{k}\$ is also a divisor of \$n\$.

   This is what Oscar also said, and it allows to restrict the search for divisors to the interval \$1\dots \sqrt n\$. The "problem" is that \$k\$ and \$\frac{n}{k}\$ can have different oddity.

2. If \$ k \$ is an odd divisor of an even number \$n\$ then \$k\$ is also an odd divisor of \$\frac{n}{2}\$.

Therefore, we can remove all even factors of \$n\$ first, and then find odd divisors in the reduced (odd) number. This makes the code simpler (because all divisors are odd) and faster for even numbers (a smaller \$n\$ means less trial divisions):

def oddDivisorSum(n):
    """Return the sum of odd divisors of n."""
    while n % 2 == 0:
        n //= 2
    sum = 0
    for k in range(1, int(n ** .5) + 1, 2):
        if n % k == 0:
            sum += k
            if n // k != k:
                sum += n // k
    return sum

Answer 2

I heard that memoization could work, but I am not sure show how to implement it.

In Python you just use built-in support

from functools import lru_cache

@lru_cache(maxsize=None)
def ...

However, it won't get you much benefit.

The real key to this problem is understanding the structure of the factors of a number. For example, count([1610612736]) should return 4. Why?

It factors as 2²⁹ 3¹.

In general, any positive non-zero¹ integer can be written as \$n = p_1{}^{a_1} \ldots p_k{}^{a_k}\$ where the \$p_i\$ are distinct primes in exactly one way (the fundamental theorem of arithmetic). Any factor of \$n\$ has the form \$d = p_1{}^{b_1} \ldots p_k{}^{b_k}\$ where \$b_i \le a_i\$ for each \$i\$. Odd factors are those which don't have \$2\$ in their factors.

So the first thing to do is to ditch the twos:

while k % 2 == 0:
    k //= 2

Then factor into primes with multiplicity and compute the sum of divisors, which is a multiplicative function.

¹ I'm being explicit because in some cultures 0 is considered positive.

Answer 3

A simple solution for quadratic speedup is to realize that for any n, all factors x will be x<n**.5, or n divided by a different factor. With this in mind, the following instantly gives quadratic speedup.

def count(numbers):
    total = 0
    for k in numbers:
        for i in range(1, int(k**.5)+1):
            if k % i == 0:
                if k % 2 == 1:
                    total += k
                if (k//i) % 2 == 1 and i*i != k:
                    total += (k//i)
    return total