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$
Sources
- 1986: David Wells: Curious and Interesting Numbers ... (previous) ... (next): $23$
- 1997: David Wells: Curious and Interesting Numbers (2nd ed.) ... (previous) ... (next): $23$