# 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 '13 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 '13 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 '13 at 4:47
This looks heavily related to Pollock's 1850-conjecture (mathworld.wolfram.com/PollocksConjecture.html): every positive integer can be written as the sum of at most 5 tetrahedral numbers; every positive integer can be written as the sum of at most 7 octahedral numbers. –  Jack D'Aurizio Dec 26 '13 at 14:18
With the greedy approach (every time I subtract from $n$ the biggest number of the form $\frac{1}{4}\binom{2a}{3}$ or $\binom{2b}{3}$ that is $\leq n$) the first numbers that require six terms are $43,69,84,104,119,133,153,168,178,\ldots$. The first numbers that require seven terms are $183,263,328,354,\ldots$. The first numbers that require eight terms are $1002,1423,1723,1968,2292,\ldots$. The first numbers that require nine terms are $11418, 12482, 14687, 16182, 17208,\ldots$. –  Jack D'Aurizio Dec 26 '13 at 14:52