Which natural numbers can be represented as a sum of natural numbers raised to different powers?

Question

Waring's problem asks about natural numbers that can be represented as a sum of natural numbers all raised to the same power $k$. I'm wondering which natural numbers can be represented as a sum of natural numbers all raised to *different* powers?

To make this question interesting, one has to impose a few additional restrictions:

• If first powers were allowed, every natural number $n$ could be trivially represented as $n=n^1$, so all exponents must be greater than $1$
• If $1$ were allowed as a base, every natural number $n$ could be trivially represented as $n=1^{a_1}+...+1^{a_n}$, so the natural numbers summed over must all be greater than $1$

Example: $12=2^2+2^3$ (smallest number representable under the above rules that is not a perfect power)

Answer 1

I'm going to caracterize the way to represent $n$ as sum of natural numbers raised to different powers. I'll be using the residue $\text{mod} 32$ so I won't be using exponents larger than $4$. We can represent $n - (n \mod 32)$ using different powers of $2$ (raising to powers larger than $4$).

$$\begin{array}{|c|c|} \hline n \mod 32 & \text{Use:}\\ \hline 0 & 0^2+0^3+0^4 \\ \hline 1 & 3^2 + 2^3 + 2^4\\ \hline 3 & 2^2 + 15^3 + 2^4\\ \hline 4 & 2^2 + 0^3 + 0^4\\ \hline 5 & 5^2 + 0^3 + 2^4 \\ \hline 6 & 3^2 + 5^3 + 0^4\\ \hline 7 & 0^2 + 7^3 + 2^4\\ \hline 8 & 0^2 + 2^3 + 0^4\\ \hline 9 & 3^2 + 0^3 + 0^4\\ \hline 10& 3^2 + 0^3 + 15^4\\ \hline 11& 0^2 + 3^3 + 2^4\\ \hline 12& 2^2 + 2^3 + 0^4\\ \hline 13& 2^2 + 2^3 + 15^4\\ \hline 14& 3^2 + 13^3 + 2^4\\ \hline 15& 2^2 + 3^3 + 2^4\\ \hline 16& 0^2 + 0^3 + 2^4\\ \hline 17& 3^2 + 2^3 + 0^4\\ \hline 18& 3^2 + 2^3 + 15^4\\ \hline 19& 2^2 + 15^3 + 0^4\\ \hline 20& 2^2 + 0^3 + 2^4\\ \hline 21& 0^2 + 13^3 + 0^4\\ \hline 22& 3^2 + 5^3 + 2^4\\ \hline 23& 0^2 + 7^3 + 0^4\\ \hline 24& 0^2 + 2^3 + 2^4\\ \hline 25& 5^2 + 0^3 + 0^4\\ \hline 26& 5^2 + 15^3 + 0^4\\ \hline 27& 0^2 + 3^3 + 0^4\\ \hline 28& 2^2 + 2^3 + 2^4\\ \hline 29& 0^2 + 5^3 + 0^4\\ \hline 30& 3^2 + 13^3 + 0^4\\ \hline 31& 2^2 + 3^3 + 0^4\\ \hline \end{array}$$

This means that the amount of numbers that cannot be expressed as sum of powers is finite (and bounded by 50000 aprox)

Answer 2

Every number divisible by $4$ can be written this way, by computing the binary expansion of $n$ and then adding $2^k$ if the $(k+1)$th digit is 1 in the expansion. Similarly you can express any odd number of the form $n+9$ where $n \geq 0$ is divisible by $8$. Not sure how to get the complete characterization of all numbers that can be written this way.