# What is the maximum number of distinct positive integer's square that sums up to $2002$?

What is the maximum number of distinct positive integer's square that sums up to $2002$ ?

My tries:

$$\frac{n(n+1)(2n+1)}{6} = 2002$$ $$\implies n\approx 17$$ but am clueless as to how to proceed any further.

• Id $0^2$ allowed? And is $(-1)^2$ counted distinct from $1^2$ because $-1\ne 1$ or counted as same because $(-1)^201^2$? – Hagen von Eitzen Jul 14 '17 at 17:46
• @HagenvonEitzen no, the integers are supposed to be positive. – ami_ba Jul 14 '17 at 17:48
• I read the question as: Maximize $n$ such that $x_1^2 + \cdots + x_n^2 = 2002$ where $x_i \in \mathbb N^*$. – lhf Jul 14 '17 at 17:51
• @lhf Yes. That's correct. – ami_ba Jul 14 '17 at 17:53
• My first guess would be $$2002=2109-107=\sum_{k=1}^{18}k^2-(1^2+5^2+9^2).$$ Fifteen squares. May be approaching from the other direction allows improvements? This was partly motivated by a result due to Sprague that all the integers $>128$ (and many below that threshold) can be written as a sum of distinct squares. $107$ was not quite large enough, but in that set anyway. As it turned out, approaching $2002$ from above lead to a better solution. – Jyrki Lahtonen Jul 14 '17 at 18:06

From $\frac {17(17+1)(2\cdot 17+1)}6 \lt 2002 \lt \frac {18(18+1)(2\cdot 18+1)}6$ you can conclude that at most $17$ distinct squares can be chosen to sum to $2002$ because the smallest $18$ add up to too much. Now you need to show that you can find $17$. If we were asked the same question for $34$ we could conclude from $1^2+2^2+3^2+4^2$ that it was at most $4$, but in fact the best we can do is $3^2+5^2$ for two. We have $\frac {17(17+1)(2\cdot 17+1)}6=1785$ so you need to increase the sum by $217$. If we delete $a^2$ from the list and add $b^2$ we want $b^2-a^2=217=(b-a)(b+a)=7\cdot 31$, which gives $b=19,a=12$ and our list is all the numbers from $1$ to $17$ except $12$ plus $19$
Your estimate gives an upper bound: Even the smallest sum obtainable from $18$ distinct positive squares is $1^2+2^2+\ldots+18^2=2109>2002$, hence we can have at most $17$ squares.
Let's try to find a solution with $17$ squares. If $k\le 17$ is the first number the sequence $x_1<x_2<\ldots< x_{17}$ omits, then $x_1^2+\ldots +x_{17}^2\ge 2109 -k^2$. We conclude $k\ge 11$ and want to solve $$x_{11}^2+\ldots +x_{17}^2=2002-(1^2+2^2+\ldots+10^2)=1617$$ Also, $2109-k^2=2002$ has no integer solution, so that there must be at least a second omitted numbre $l$. Can we find $l>k\ge 11$ such that $1^2+2^2+\ldots+19^2-k^2-l^2=2002$? That is, $k^2+l^2=468$? First try, $468-11^2$ is not a square. But the second try gives $468-12^2=18^2$. So $$2002=1^2+2^2+3^3+4^4+5^2+6^2+7^2+8^2+9^2+10^2+11^2+13^2+14^2+15^2+16^2+17^2+19^2$$ shows that we can write $2002$ a sum of $17$ distinct positive squares.
A different approach. We have $$6\cdot 2002 = 2^2\cdot 3\cdot 7\cdot 11\cdot 13 \tag{1}$$ but there is no way of regrouping the terms in the RHS as $a\cdot b\cdot c$ with $a,b,c\in\mathbb{N}$, $b\approx a$ and $c\approx 2b$ (that would lead to $b\approx 18$, but the closest we can get through factors in the RHS is $21=3\cdot 7$ or $22=2\cdot 11$) so $2002$ is not a number of the form $1^2+2^2+\ldots+m^2$.