How many ways are there to write $173$ as a sum of squares

contest-mathelementary-number-theorysums-of-squares

Q. How many ways are there to write $173$ as a sum of squares of natural numbers?

A friend of mine recently asked me this question, and I haven't been able to figure it out fully. I know that $$2^2+3^2+4^2+12^2=2^2+5^2+12^2=2^2+13^2=\sum_{k=1}^{173} 1^2=173.$$ So, there are atleast four ways to write $173$ as a sum of squares. However, I haven't found any other solutions. I also haven't been able to prove that these are the only solutions. If we had something like $a^2+b^2=173$ where we were restricted to only $2$ numbers in the LHS, perhaps we could use modular arithmetic and find all solutions. However, the question doesn't say "How many ways are there to write $173$ as a sum of two squares?". The fact that the LHS could have anywhere between $2$ and $173$ natural numbers complicates things a bit. Any help would be appreciated.

Note: I am adding the "contest-math" tag as my friend said that he saw this question on a video that was intended for olympiad practice. However, I haven't been able to find the video.

Best Answer

The python code

target = 173
squares = [i**2 for i in range(1, int((target)**(1/2))+1)]

ways = {i: 0 for i in range(target+1)}
# Every sum starts at zero (if there are no squares added)
ways[0] = 1

for sq in squares:
    for total in range(sq, target+1):
        # We can add the square to the previous total-sq to get total
        ways[total] += ways[total - sq]

print(ways[target])

returns that there are 13027 ways to get 173 as a sum of squares.

See also A001156.

Related Question