Python function to find all integers between two numbers whose sum of squared divisors is a perfect square

Question

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.

The result will be an array of arrays, each subarray having two elements, first the number whose squared divisors is a square and then the sum of the squared divisors.

I have a working function as follows, however it does not execute fast enough.

from math import sqrt
def list_squared(m, n):
 def D(x):return sum(i**2 for i in range(1,x+1) if not x%i)
 return [[i,D(i)] for i in range(m,n) if sqrt(D(i)).is_integer()]

I have also tried a for loop instead of list comprehension, using a variable to save the output of the D function so it doesn't get called twice, and it didn't help. I have no experience optimizing code for speed.

from math import sqrt
def list_squared(m, n):
 def D(x):return sum(i**2 for i in range(1,x+1) if not x%i)
 z = []
 for i in range(m,n):
 x = D(i)
 if sqrt(x).is_integer():
 z.append([i,x])
 return z

---

#Examples
list_squared(1, 250) --> [[1, 1], [42, 2500], [246, 84100]]
list_squared(42, 250) --> [[42, 2500], [246, 84100]]

• Sᴀᴍ Onᴇᴌᴀ: "however it does not execute fast enough" - is a time limit exceeded? you could add the tag time-limit-exceeded
• Cyber17C: Yes, a time limit is exceeded on the executing server, however it does not state what that limit is, only that I surpassed it and to optimize my code more.

Answer 1

There is no need to go up to the number to know its factor, going up to the sqrt is enough:

def D(x):
 return sum(i**2 + int(((x / i) ** 2 if i * i != x else 0)) for i in range(1, floor(x ** 0.5) + 1) if not x%i)

That should speed up quite a bit the computation if you are dealing with big numbers

• Cyber17C: Replacing your D(x) with mine returns the following output for the first test case list_squared(1,250): [[4, 25.0], [9, 100.0], [25, 676.0], [42, 2500.0], [49, 2500.0], [121, 14884.0], [169, 28900.0], [246, 84100.0]] should equal [[1, 1], [42, 2500], [246, 84100]] After changing the floats to integers it still is picking up extraneous numbers for some reason, not sure what the error is.
• juvian: @Cyber17C my bad, for numbers that were a perfect square it was adding its sqrt factor twice, fixed now
• Cyber17C: The new solution works and scales much better than mine, thank you!
• juvian: @Cyber17C no problem. Consider k = m - n, your previous solution was O(k^2) while this one is O(k sqrt k) = O(k^1.5)