# Numbers which are not the sum of distinct squares

We are defining square factorization as representation a positive natural number as sum of squares of different positive, integer numbers. For example $5 = 1^2 +2^2$ and $5$ has no more representation. But one number can possess more representations, eg. $30$.

$$30 = 1^2 + 2^2 + 5^2 = 1^2 +2^2 + 3^2 + 4^2$$

Sometimes $n$ has no representation, eg. $8$. If square factorization for $n$ is impossible, we call $n$ indecomposable, so $8$ is indecomposable. Because it is a significant part of other proof I began to wonder, how can we know there is finite number of indecomposable numbers. Of course, it is well know fact, but I have still problem with proving that.

How to show that any number greater than $128$ can be written as sum of distinct squares — for all $n > 128$ square factorization exist?

First, you show that you can express all numbers $129$ though something convenient as a sum of distinct squares just by making a list. I will choose $4900$ and assume that we have a list that runs that high. We do the proof by strong induction. Assume that all numbers in the range $[129,k]$ can be expressed as a sum of distinct squares, where $k \ge 4900$. We shall show that $k+1$ can be so expressed. Let $m = \lfloor \sqrt {k+1} \rfloor -1$. We can express $k+1=m^2+p$, where $p \ge 129$, so it can be expressed as a sum of distinct squares. Since $p \lt m^2$, there is no conflict with the new square, and $k+1$ can be expressed as a sum of distinct squares. You could lower the bound of the specific list below $3600$ if you think harder about what square to subtract. I chose $3600$ because the spacing of squares attains $129$ at that point.
Added: the list you make can run only through $[129,297]$. We can be lazier in the first part with more work in the second. $297$ is a risk because $297=169+128$, so the largest square you can subtract and stay larger than $129$ is $144$ and the expression for $153$ could involve $144$. In fact $144+9=153$, but you can also do $100+49+4$. Starting with $298$ you can always subtract a square that leaves at least $129$ and is greater than half the starting number, so the strong induction goes through.