Close to he requirement in the original question: Waring's problem which generalizes Lagranges's four-square theorem. Every positive integer can be expresses as a sum of 9 cubes, a sum of 19 fourth powers etc. For the $k$-th powers the number of summands required, denoted $g(k)$, was a heuristic guess, $g(k) = 2^k + [ (\frac32)^k ]- 2$ and some variations of this. Though Hilbert proved $g(k)$ is finite before 1910 actual specific values were proved decades later. The reason I know this is because one of the persons who 'nailed the last nail into the coffin" of this problem in 1980s was working where I started my PhD.
The number of summands is very high for low numbers because (heuristically) you have only 1 and $2^k$ to use. For 4-th powers 79 is the culprit, needing fifteen 1's and four 16's.
So this lead to related another natural question: as numbers needing that many summands are small in size they may be a finite number of exceptions. Define $G(k)$ as the number of summands needed for expressing every sufficiently large integer as sum of $k$-th powers (i.e. treat 79 as an exception for the case of fourth powers). $G(4)$ is known to be 16.
