# How many ways are there to write $173$ as a sum 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.

• Do it like you would the famous change for a dollar problem. Your "coins" have value $\{1,4, 9, 16, \cdots, 169\}$ and your "dollar" is worth $173$.
– lulu
Commented Mar 14, 2023 at 12:30
• if $s=x_1^2+\cdots+x_n^2<173$ then this can be augmented to a sum of squares adding up to $173$ bei adding some $1^2$ to $s$ Commented Mar 14, 2023 at 12:32
• Agreed on terminology, if it was two squares and since $173 \equiv \, 1 \: \text{Mod} \, 4$ there will only be one set of two integers. Commented Mar 14, 2023 at 12:38
• Should say, there are lots and lots of solutions. $173=13^2+1^2+1^2+1^2+1^2$ for instance. I did it fast (and, therefore, possibly incorrectly) and got an answer over $1,000$.
– lulu
Commented Mar 14, 2023 at 12:41

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.

• @lulu no I am not, for target=10 we get an answer of 4 and $10=3^2+1^2$$=2\cdot 2^2 + 2\cdot 1^2$$= 2^2 + 6\cdot 1^2$$= 10\cdot 1^2$. The main loop over squares ensures that the possibilities of something like $13^2$ are always added later than $2^2$. Commented Mar 14, 2023 at 12:48
• My mistake. Since I invoked the "change of a dollar problem" I mentally reset the target number to $100$. When I put in the correct value of $173$ my answer matches yours. here. I'll delete my first comment.