Find numbers whose factors, when squared, sum to a perfect square

Question

I need help optimizing my Python code for CodeWars Integers: Recreation One Kata.

We are given a range of numbers and we have to return the number and the sum of the divisors squared that is a square itself.

Divisors of 42 are : 1, 2, 3, 6, 7, 14, 21, 42. These divisors squared are: 1, 4, 9, 36, 49, 196, 441, 1764. The sum of the squared divisors is 2500 which is 50 * 50, a square!

Given two integers m, n (1 <= m <= n) we want to find all integers between m and n whose sum of squared divisors is itself a square. 42 is such a number.

My code works for individual tests, but it times out when submitting:

import math
def list_squared(m, n):
    sum=0
    total=[]
    for x in range(m,n+1):
        for y in range(1,x+1):
            if x%y==0:
                sum+=y**2
        if math.sqrt(sum).is_integer():
            total.append([x,sum])
        sum=0
    return total

Answer 1

Various details

You initialise sum = 0 before the loop and then at the end of each iteration making it slightly harder to understand how it is being used and how one iteration affects another. It would be clearer (and shorter) to initialise it at the beginning of each iteration.

Also, sum is a Python built-in: by defining a variable with the same name, you are somehow hiding the built-in which we may want to use later on. A more precise name such as div_sum could be used.

You may want to divide your logic into smaller functions which are easier to maintain but also to document and to test. For instance:

def get_divisor_squared_sum(n):
    div_sum = 0
    for y in range(1, n+1):
        if n % y == 0:
            div_sum += y**2
    return div_sum

assert get_divisor_squared_sum(1) == 1*1
assert get_divisor_squared_sum(2) == 1*1 + 2*2
assert get_divisor_squared_sum(6) == 1*1 + 2*2 + 3*3 + 6*6
assert get_divisor_squared_sum(9) == 1*1 + 3*3 + 9*9

def list_squared(m, n):
    total=[]
    for x in range(m, n+1):
        div_sum = get_divisor_squared_sum(x)
        if math.sqrt(div_sum).is_integer():
            total.append([x, div_sum])
    return total

Then, it gets easier to improve one function indedepently of how it is being used. For instance, we could improve get_divisor_squared_sum in various ways. First, we could use the sum builtin.

def get_divisor_squared_sum(n):
    return sum(d**2 for d in range(1, n+1) if n % d == 0)

Also, and probably more important, we could stop looking for divisors much earlier as mentionned in other answers (I will not repeat what has been said but this one of the best optimisations you could put in place).

I'm not sure about the exact expectations of the CodeWars challenge but I think the return type of your function could be slightly more Pythonic: instead of returning list of lists, I'd rather return a list of tuples. I highly recommend the excellent "Lists vs. Tuples" post from Ned Batchelder 's excellent blog to see the technical and cultural differences between the 2.

def list_squared(m, n):
    total=[]
    for x in range(m, n+1):
        div_sum = get_divisor_squared_sum(x)
        if math.sqrt(div_sum).is_integer():
            total.append((x, div_sum))
    return total

Answer 2

Finding all numbers' factors by trial division is going to be slow. We can make it faster by stopping when we reach √x, and adding both y and x/y to the list of factors (when y ≠ x/y, of course).

Look at other implementations of factorisation to improve that part of your code. You might want to decompose x to its prime factors, and synthesize all the composite factors from those primes. We can generate primes up to n using a sieve, before beginning the loop.

Consider splitting out some functions to factorise the number, and to test the sum-of-squares property. Then list_squared can be simply

def list_squared(m, n):
    return [x if sum_squared_is_square(factors(x)) for x in range(m, n+1)]

Minor style gripe: no need to compare a boolean with ==True - just write if math.sqrt(sum(squared)).is_integer():.

Answer 3

We can significantly improve performance by optimizing divisors searching. It suffices to check first sqrt(x) divisors, because for each divisor d <= math.sqrt(x), any complementary divisor equals to x // d.

---

We don't need these lists to store intermediate data because the sum may be calculated in one pass for each x. Lists complicate your solution significantly.

---

Don't import modules in place. Put imports on top of the file (pep8).

---

import math

def list_squared(m, n):     
    ans = []
    for k in range(m, n + 1):
        divsum = 1
        if k > 1:
            divsum += k * k

        d = 2
        while d * d < k:
            if k % d == 0:
                divsum += d * d + (k // d) * (k // d)
            d += 1
        if d * d == k:
            divsum += k
                    
        if math.sqrt(divsum).is_integer():
            ans.append([k, divsum])
    return ans