Yesterday an official delineation of solution to this task appeared (PL). I am disappointed that it's much slower than above. However, it presents me a new point of view of the problem. In conjunction with it, my idea is quite nice.
Main thing in this proof is fact, that set of indecomposable numbers is finite. Accept this as a well-known fact, or if you don't want, look here.
Helpful in understanding, it may be observation, if $n$ isn't inter-grown, and $k(n) = x$ then $n + (x+1)^2$ isn't inter-grown.
Inter-grown
First observation should be, than $n = \sum_{i=1}^{x}{i^2}$ isn't inter-grown. $n$ uses all squares not larger than $x^2$, so if $n' > n$ it's impossible to present $n'$ using only lower, than $x^2$. Emphasize that $k(\sum_{i=1}^{x}{i^2}) = x$. Now we should take advantage of the observation from question. If $x$ is the smallest number, witch satisfies the inequality $\sum_{i=1}^{x} i^2 \geq n$, then $k(n) \geq x$. So, we can predicate, that $n$ is inter-grown, if $k(n) > x$.
Value of $k(n)$
Now, let's look at it from other side. Let $n' = \left(\sum_{i=1}^{x} i^2\right) - n$. In this case we can present $n$ as sum of different squares (not bigger than $x^2$) if and only if $n'$ isn't indecomposable. Simply subtract $\left(\sum_{i=1}^{x} i^2\right) - n'$, if $n'$ is indecomposable it's impossible. That's obvious. If $n'$ is indecomposable we have to check $n'' = \left(\sum_{i=1}^{x+1} i^2\right) - n$ in the same way. We need to check, until we find decomposable $n^{*}$. But, wait! The greatest indecomposable number is 128, so $(x+1)^2 > 128 \wedge n'' = n' + (x+1)^2$ guarantees that $n''$ is decomposable! So from sufficiently large $n$, $k(n)=x~~\dot{\vee}~~k(n) = x+1$.
It's not hard to see, if and only if $n'$ is indecomposable, $n$ is inter-grown.
Counting isn't hard too. As expected, we have to remember for small $n$, groups can overlap and we have to count it by computer. After we can just add 31 with each subsequent square. The last group not necessarily add 31, cause not all elements have to be in, but they occur on a regular relative position ($n' \in \lbrace 2, 3, 6, 7, 8, 11, 12, 15,..., 128\rbrace$, so it's obvious, why.) and it's really easy to count. I don't think I have to describe it.
Legendre gave the following answer, which he could not prove (Gauss gave the first proof of the 3-squares theorem). For the sake of simplicity I will only cover the case of numbers $c \equiv 5 \bmod 8$. In this case consider the equivalence classes of forms with discriminant $-4c$; like Legendre, we will consider equivalence with respect to the action of GL$_2({\mathbb Z})$. Let $P$ denote the form classes that represent primes $p \equiv 1 \bmod 4$, and $Q$ those that represent primes $q \equiv 3 \bmod 4$. Then the number of classes $P$ is equal to that of classes $Q$, and to the number of ways in which $c$ can be written as a sum of three squares.
If $c = 29$, the classes $P$ are $x^2 + 29y^2$ and $5x^2 + 2xy + 6y^2$, and these correspond to the two distinct ways of writing $29$ as a sum of three squares: $29 = 0^2 + 2^2 + 5^2 = 2^2 + 3^2 + 4^2$.
Legendre conjectured similar formulas for other values of $c$, which were later proved by Gauss, but using classes with respect to the action of SL$_2({\mathbb Z})$.
Best Answer
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.