How to tell if number can be writen as sum of n different squares?

Admin 1
Viewed 547

I know how to check if the number can be represented as the sum of two squares with a brute-force approach.

def sumSquare( n) :
    i = 1
    while i * i <= n :
        j = 1
        while(j * j <= n) :
            if (i * i + j * j == n) :
                print(i, "^2 + ", j , "^2" )
                return True
            j = j + 1
        i = i + 1

    return False

But how to do it for n distinct positive integers. So the question would be:

Function which checks if the number can be written as sum of 'n' different squares

I have some examples.

For e.g.

  1. is_sum_of_squares(18, 2) would be false because 18 can be written as the sum of two squares (3^2 + 3^2) but they are not distinct.
  2. (38,3) would be true because 5^2+3^2+2^2 = 38 and 5!=3!=2.

I can't extend the if condition for more values. I think it could be done with recursion, but I have problems with it.

I found this function very useful since it finds the number of squares the number can be split into.

def findMinSquares(n):
    T = [0] * (n + 1)
    for i in range(n + 1):
        T[i] = i
        j = 1
        while j * j <= i:
            T[i] = min(T[i], 1 + T[i - j * j])
            j += 1

    return T[n]

But again I can't do it with recursion. Sadly I can't wrap my head around it. We started learning it a few weeks ago (I am in high school) and it is so different from the iterative approach.

recursion math python
2 Answers

Recursive approach:

def is_sum_of_squares(x, n, used=None):
    x_sqrt = int(x**0.5)
    if n == 1:
        if x_sqrt**2 == x:
            return used.union([x_sqrt])
        return None
    used = used or set()
    for i in set(range(max(used, default=0)+1, int((x/n)**0.5))):
        squares = is_sum_of_squares(x-i**2, n-1, used.union([i]))
        if squares:
            return squares
    return None
user_2716410

Quite a compelling exercise. I have attempted solving it using recursion in a form of backtracking. Start with an empty list, run a for loop to add numbers to it from 1 to max feasible (square root of target number) and for each added number continue with recursion. Once the list reaches the required size n, validate the result. If the result is incorrect, backtrack by removing the last number. Not sure if it is 100% correct though. In terms of speed, I tried it on the (1000,13) input and the process finished reasonably fast (3-4s).

def is_sum_of_squares(num, count):
    max_num = int(num ** 0.5)
    return backtrack([], num, max_num, count)


def backtrack(candidates, target, max_num, count):
    """
    candidates = list of ints of max length <count>
    target = sum of squares of <count> nonidentical numbers
    max_num =  square root of target, rounded
    count = desired size of candidates list
    """
    result_num = sum([x * x for x in candidates])  # calculate sum of squares
    if result_num > target:  # if sum exceeded target number stop recursion
        return False
    if len(candidates) == count:  # if candidates reach desired length, check if result is valid and return result
        result = result_num == target
        if result:  # print for result sense check, can be removed
            print("Found: ", candidates)
        return result
    for i in range(1, max_num + 1):  # cycle from 1 to max feasible number
        if candidates and i <= candidates[-1]:
            # for non empty list, skip numbers smaller than the last number.
            # allow only ascending order to eliminate duplicates
            continue
        candidates.append(i)  # add number to list
        if backtrack(candidates, target, max_num, count):  # next recursion
            return True
        candidates.pop()  # if combination was not valid then backtrack and remove the last number
    return False


assert(is_sum_of_squares(38, 3))
assert(is_sum_of_squares(30, 3))
assert(is_sum_of_squares(30, 4))
assert(is_sum_of_squares(36, 1))
assert not(is_sum_of_squares(35, 1))
assert not(is_sum_of_squares(18, 2))
assert not(is_sum_of_squares(1000, 13))
user_174468010
Related