# 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?

-
This and this might be of interest. –  dtldarek Feb 25 at 10:54
There is no "obvious reason" as Waring-like results are usually difficult. In addition to "Waring's problem" you might also want to search for the Hardy-Littlewood "circle method" if you want to learn how to prove these kinds of results. –  Noah Snyder Apr 11 at 1:12
@NoahSnyder I've heard of the circle method, but was hoping for a more elementary argument here. If answering this requires a sever-year digression in my mathematical study into analytic number theory, I probably won't bother. –  Alex Becker Apr 11 at 4:47