Can every number be written as a small sum of sums of squares? In a practice for a programming competition, one problem asked us to find the smallest number of pyramids which can be built using exactly $n$ blocks, where pyramids have either $k\times k, (k-1)\times (k-1),\ldots,1\times 1$ blocks on each level or $2k\times 2k, 2(k-1)\times 2(k-1),\ldots,2\times 2$ blocks on each level. Note that the first type of pyramid has
$$\sum\limits_{i=1}^k i^2 = \frac{k(k+1)(2k+1)}{6}$$
blocks while the second has
$$\sum\limits_{i=1}^k (2i)^2 = \frac23 k(k+1)(2k+1).$$
Equivalently, we want to write $n$ as a sum of numbers of this form, using as few as possible. The official solution to this problem had an exponential runtime in the minimal number of pyramids, but noted that this was not problematic as the minimal number of pyramids is always at most $6$. I see no obvious reason for this, or even an obvious reason why the minimal number of pyramids should be bounded. Can someone provide a proof?
 A: This concerns showing the minimal number of pyramaids is bounded. I don't know the effective value of the bound, as it depends on a theorem of Hua which implies that every sufficiently large integer is the sum of nine or ten cubes of primes. 
Let $s(n)=n(n+1)(2n+1)$ which is $6$ times the number of blocks of a type $1$ pyramid. Then we have the identity
$$s(n+1)+22s(n)+s(n-1)=6(2n+1)^3. \tag{1}$$
Now supposing we have a given large number $M,$ we write $M=6k+r$ with $0 \le r <6$. The result of Hua then says we can write $k$ as a sum of nine or ten cubes of primes. If $2$ is one of the primes we can get the $6*2^3$ using a bounded number of pyramids. The other primes are odd cubes $p^3$ and each $6p^3$ can each be obtained by a bounded number of pyramaids using $(1)$. The remainder $r$ only needs finitely many more.
EDIT: I noticed that $(1)$ may be divided by $6$ and then gives the same relation between the numbers $t(n)=n(n+1)(2n+1)/6$ which are the counts for the type 1 pyramids. Then there is no need for writing $M=6k+r$ and one can apply Hua's result directly. Since the coefficient $22=5\cdot 4 +2$ each $t(n+1)+22t(n)+t(n-1)$ really introduces only nine pyramids, which then brings the count down a bit more. But this is not much better since a bound of say $81$ for sufficiently large $M$ is so much larger than the likely bound of $6$.
The site which I found discussing the Hua result is a paper by Koichi Kawada. The Hua result is from 1938. Kawada paper
UPDATE
There is a result of R. D. James which implies one can get all sufficiently large integers as a sum of nine of the type 1 pyramidal numbers, above called $t(n)$. This is a much better bound than that implied by the sum of cubes consequences worked out above, though it still only applies for sufficiently large  integers. If anyone wants to check the correspondence, it is that $t(x)$ matches the polynomial $P(x)$ of James' paper provided $a=2,\ b=c=1.$
Jame's paper is on JSTOR, with the following link. One gets a preview page, which contains enough to see the result, and it seems one can read on line for free if one gets a JSTOR account. The link:
http://www.jstor.org/discover/10.2307/2370934?uid=3739832&uid=2129&uid=2&uid=70&uid=4&uid=3739256&sid=21104342222973
A: Not quite an answer, but a start: It's easy to show there are infinitely many integers n which require at least four pyramids: The number of blocks in a pyramid is always 0 (modulo 5), 1 (modulo 5) or 4 (modulo 5). Actually, one in five numbers is 1 (modulo 5), one in five is 4 (modulo 5) and 3 in 5 are 0 (modulo 5). To get a sum that is 2 (modulo 5), we need to add 0 + 1 + 1 (modulo 5) or 4 + 4 + 4 (modulo 5). 
k(k+1)(2k+1)/6 is about k^3/3, so there are about (3n)^(1/3) of those less than n.
k(k+1)(2k+1)*2/3 is about 4k^3/3, so about (3n/4)^(1/3) of those are less than n. 
The total number of values < n is about 2.351 n^(1/3). About 0.47 n^(1/3) are 1 (modulo 5), about 0.47 n^(1/3) are 4 (modulo 5), about 1.41 n^(1/3) are 0 modulo 5. 
There are about (0.47 * 0.47 * 1.41 / 2)n sums of the form 0 + 1 + 1 (modulo 5), and about (0.47 * 0.47 * 0.47 / 6)n sums of the form 4 + 4 + 4 (modulo 5). This adds up to about 0.173n sums equal to 2 (modulo 5); many of these are > n, so the number of sums less than n are fewer than that. But there are 0.2 numbers <= n that are 2 modulo 5, so many of these cannot be the sums of three pyramids. 
I checked that up to n = 1 billion, about 69% of all numbers are the sum of at most three pyramids. The same is true for n = 100 million, so that percentage of numbers needing four pyramids seems quite constant. All numbers up to 1 billion are the sum of four pyramids with the exceptions n = 108, n = 247 and n = 1007 which need 5. 
Some more statistics: Of the numbers from 1 to 1 billion, 
69.58% are the sum of three pyramids
89.48% are the sum of three pyramids and the number 1
97.47% are the sum of three pyramids and the number 1 or 4
98.78% are the sum of three pyramids and the number 1, 4 or 5
99.36% are the sum of three pyramids and the number 1, 4, 5 or 20
99.77% are the sum of three pyramids and the number 1, 4, 5, 20 or 14
All but the three mentioned above are the sum of three pyramids, and a pyramid up to 650. 

This makes it quite unlikely that any numbers other than 108, 247 and 1007 would require more than four pyramids, but doesn't help one bit proving it. 
