numbers representable as sums of perfect powers

Question

Here is my little research:

$4=2^2$

$8=2^3$

$9=3^2$

$12=2^3+2^2$

$13=3^2+2^2$

$16=2^3+2^3$

$17=3^2+2^2+2^2$

$18=3^2+3^2$

$20=2^3+2^3+2^2$

$21=2^3+3^2+2^2$

$24=2^3+2^3+2^3$

and it seems every number $\ge 24$ is also representable as a sum of perfect powers (I checked up to 1000 using computer).

Is this known?

Any ideas how to prove it?

Answer 1

In a different direction from orlp's answer (now deleted): It seems you allow repeated powers. Assuming that exponents are required to be greater than or equal to $2$, observe that $2^2 = 4$ and $3^2 = 9$, and the Chicken McNuggets problem with $4$ and $9$ yields an upper bound of $4 \times 9 - 4 - 9 = 23$ for the numbers that cannot be expressed as a combination of those two numbers alone.

ETA: All other perfect powers of larger primes are $25$ or greater and therefore do not bear on this upper bound.

Answer 2

Here is a quick way that works for $n≥54$.

Writing the number in base $2$ gives such a sum, though of course $2^0=1$, or $2^1=2$ might appear.

If the number is divisible by $4$, then neither $2^0$ nor $2^1$ appears so we are done.

If the number is $1\pmod 4$ and at least $9$ then subtract $3^2=9$.

If the number is $3\pmod 4$ and at least $27$ then subtract $3^3$.

If the number is even but not divisible by $4$ then it is twice an odd number so we can reduce to that case.

In this way we are done if $n≥54$. Case by case analysis handles most lower $n$ as well.