0
$\begingroup$

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.

$\endgroup$
4
  • 5
    $\begingroup$ 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$. $\endgroup$
    – lulu
    Commented Mar 14, 2023 at 12:30
  • 1
    $\begingroup$ 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$ $\endgroup$
    – miracle173
    Commented Mar 14, 2023 at 12:32
  • $\begingroup$ 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. $\endgroup$
    – asymptotic
    Commented Mar 14, 2023 at 12:38
  • 1
    $\begingroup$ 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$. $\endgroup$
    – lulu
    Commented Mar 14, 2023 at 12:41

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ @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$. $\endgroup$ Commented Mar 14, 2023 at 12:48
  • 1
    $\begingroup$ 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. $\endgroup$
    – lulu
    Commented Mar 14, 2023 at 12:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .