1
\$\begingroup\$

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]]
\$\endgroup\$
  • \$\begingroup\$ "however it does not execute fast enough" - is a time limit exceeded? you could add the tag time-limit-exceeded \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ May 17 '18 at 18:52
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Cyber17C May 17 '18 at 18:56
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Cyber17C May 17 '18 at 19:04
  • \$\begingroup\$ @Cyber17C my bad, for numbers that were a perfect square it was adding its sqrt factor twice, fixed now \$\endgroup\$ – juvian May 17 '18 at 19:19
  • \$\begingroup\$ The new solution works and scales much better than mine, thank you! \$\endgroup\$ – Cyber17C May 17 '18 at 19:33
  • \$\begingroup\$ @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) \$\endgroup\$ – juvian May 17 '18 at 19:37

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.