9
\$\begingroup\$

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
\$\endgroup\$
  • 4
    \$\begingroup\$ I am not sure why someone voted to close as off-topic (broken code). As far as I can see, the code works correctly. Being too slow/inefficient for a programming competition is a valid (and frequent) reason to ask for a code review. \$\endgroup\$ – Martin R Oct 2 '17 at 5:20
11
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ it might be faster to compute gcd(n, 2^64) and divide n by that, not sure though \$\endgroup\$ – Oscar Smith Oct 2 '17 at 13:40
  • 1
    \$\begingroup\$ @OscarSmith, if you're talking about micro-optimising the while n % 2 == 0: n //= 2, the faster alternative would be n //= -n & n. But the chances that that loop is the bottleneck are extremely slim. \$\endgroup\$ – Peter Taylor Oct 2 '17 at 14:18
  • 1
    \$\begingroup\$ @OscarSmith: I haven't benchmarked it (and Peter is surely right). I think I have seen gcd implementations which remove common factors of two first, which would be the opposite of what you suggest. \$\endgroup\$ – Martin R Oct 2 '17 at 14:26
  • \$\begingroup\$ Thanks for the detailed help. I'll try it out and benchmark it, see if it makes a difference. :) \$\endgroup\$ – CatIntheHatter Oct 3 '17 at 5:38
6
\$\begingroup\$

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 229 31.

In general, any positive non-zero1 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.

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

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Unless I am mistaken, this would for example not find the odd divisor 13 of 26 (because the iteration stops at i=3). Also the square root might be counted twice as a divisor. – Did you run this with the sample data K = [3, 4, 20] from the question? \$\endgroup\$ – Martin R Oct 2 '17 at 5:03
  • \$\begingroup\$ oops, you're right, edited \$\endgroup\$ – Oscar Smith Oct 2 '17 at 5:09
  • \$\begingroup\$ Still does not work, count([3, 4, 10]) returns 1. – Btw, range excludes the upper bound. \$\endgroup\$ – Martin R Oct 2 '17 at 5:16
  • 1
    \$\begingroup\$ this has been embarrassing \$\endgroup\$ – Oscar Smith Oct 2 '17 at 5:22
  • 1
    \$\begingroup\$ Now count([6]) returns 3 instead of 4. – I don't want to sound rude, but I would suggest to run more test cases, comparing your output against the result of the original function from the question. \$\endgroup\$ – Martin R Oct 2 '17 at 5:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.