3
$\begingroup$

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)

$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

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)

$\endgroup$
6
  • $\begingroup$ This may well be a stupid question, but how did you get the $50000$ approximation? Is it because of the choice of residue? $\endgroup$
    – recursive recursion
    Commented Aug 14, 2014 at 21:53
  • $\begingroup$ @recursiverecursion: note the value for $18$, (which is $50642$ and I think is the largest in the table) so you wouldn't have to check higher than that. As only three of the entries use $15^4$, you could argue the number to check is about $10$ times lower. Just add up the values in the table and divide by $32$ $\endgroup$
    – Ross Millikan
    Commented Aug 14, 2014 at 22:02
  • $\begingroup$ No, it's because for some of those numbers I'm using $3^2+2^3+15^4$ wich is a bit over $50000$ (50642 to be precise), so you'd need $n$ to be over that number to use that representation. I don't know if there's a better way to express it, but if there is such a way, it would involve using exponents higher than $4$. $\endgroup$
    – Darth Geek
    Commented Aug 14, 2014 at 22:02
  • $\begingroup$ That's it. Amazing derivation, thank you! $\endgroup$
    – user139000
    Commented Aug 18, 2014 at 17:41
  • $\begingroup$ @pew Thanks! It took me quite a while... =P $\endgroup$
    – Darth Geek
    Commented Aug 18, 2014 at 17:47
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.