# 23 is Largest Integer not Sum of Distinct Perfect Powers

## Theorem

The largest integer which cannot be expressed as the sum of distinct perfect powers is $23$.

## Proof

The first few perfect powers are:

$1, 4, 8, 9, 16, 25, 27, 32, \dots$

First we show that $23$ cannot be expressed as the sum of distinct perfect powers.

Only $1, 4, 8, 9, 16$ are perfect powers less than $23$.

Suppose $23$ can be so expressed.

Since $1 + 4 + 8 + 9 = 22 < 23$, $16$ must be used in the sum.

However $23 - 16 = 7$ cannot be expressed as a sum of $1$ and $4$.

Thus $23$ cannot be expressed as the sum of distinct perfect powers.

$\Box$

Now we show that all numbers greater than $23$ can be so expressed.

By Richert's Theorem, we just need to show:

For any $23 < n \le 23 + 32$, $n$ can be expressed as a sum of distinct elements in $\set {1, 4, 8, 9, 16, 25, 27}$
$s_{i + 1} \le 2 s_i$ for every $i \ge 7$, where $s_i$ is the $i$th perfect power

Verification of the first statement is included in the bottom of this proof.

To verify the second statement:

Let $i \ge 7$.

Let $m$ be the integer satisfying:

$2^{m + 1} > s_i \ge 2^m$

Note that $2^{m + 1}$ is also a perfect power.

There must be a perfect power greater than $s_i$ but not greater than $2^{m + 1}$.

Thus:

$s_{i + 1} \le 2^{m + 1} = 2 \cdot 2^m \le 2 s_i$

Therefore $23$ is the largest integer that cannot be expressed as the sum of distinct perfect powers..

$\Box$

Here is $23 < n \le 55$ expressed as a sum of distinct elements in $\set {1, 4, 8, 9, 16, 25, 27}$:

 $\ds 24$ $=$ $\ds 16 + 8$ $\ds 25$ $=$ $\ds 25$ $\ds 26$ $=$ $\ds 25 + 1$ $\ds 27$ $=$ $\ds 27$ $\ds 28$ $=$ $\ds 27 + 1$ $\ds 29$ $=$ $\ds 25 + 4$ $\ds 30$ $=$ $\ds 25 + 4 + 1$ $\ds 31$ $=$ $\ds 27 + 4$ $\ds 32$ $=$ $\ds 27 + 4 + 1$ $\ds 33$ $=$ $\ds 25 + 8$ $\ds 34$ $=$ $\ds 25 + 9$ $\ds 35$ $=$ $\ds 25 + 9 + 1$ $\ds 36$ $=$ $\ds 27 + 9$ $\ds 37$ $=$ $\ds 27 + 9 + 1$ $\ds 38$ $=$ $\ds 25 + 9 + 4$ $\ds 39$ $=$ $\ds 25 + 9 + 4 + 1$ $\ds 40$ $=$ $\ds 27 + 9 + 4$ $\ds 41$ $=$ $\ds 27 + 9 + 4 + 1$ $\ds 42$ $=$ $\ds 25 + 9 + 8$ $\ds 43$ $=$ $\ds 25 + 9 + 8 + 1$ $\ds 44$ $=$ $\ds 27 + 9 + 8$ $\ds 45$ $=$ $\ds 27 + 9 + 8 + 1$ $\ds 46$ $=$ $\ds 25 + 9 + 8 + 4$ $\ds 47$ $=$ $\ds 25 + 9 + 8 + 4 + 1$ $\ds 48$ $=$ $\ds 27 + 9 + 8 + 4$ $\ds 49$ $=$ $\ds 27 + 9 + 8 + 4 + 1$ $\ds 50$ $=$ $\ds 25 + 16 + 9$ $\ds 51$ $=$ $\ds 25 + 16 + 9 + 1$ $\ds 52$ $=$ $\ds 27 + 25$ $\ds 53$ $=$ $\ds 27 + 25 + 1$ $\ds 54$ $=$ $\ds 25 + 16 + 9 + 4$ $\ds 55$ $=$ $\ds 25 + 16 + 9 + 4 + 1$

$\blacksquare$