Skip to main content
4 of 4
edited tags
Toby Speight
  • 81.7k
  • 14
  • 101
  • 308

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

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