Numbers which are not the sum of distinct squares

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.


I actually did this for fun when I was 17 (and it was mostly fun, though a bit of a grind). The way I did it was to realise that, for numbers 0 mod 4, I only needed to test up to 512, because anything after that could be written as 4 times the solution for the quarter of that number (for example, if 129 = 100 + 25 + 4, then 516 = 400 + 100 + 16). After that, numbers 1 mod 4 need to be tested up to 517 (take any solution that can be quadrupled and add 1), numbers 2 mod 4 need to be tested up to 526 (add 9 and 1), and numbers 3 mod 4 need to be tested up to 551 (add 25, 9 and 1). The grindy part was testing all those numbers.