23 is Largest Integer not Sum of Distinct Perfect Powers

From ProofWiki
Jump to navigation Jump to search

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$

We have that $m \ge 4$.

Hence $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:

$2 s_i \ge 2^{m + 1} \ge s_{i + 1}$


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}$:

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

$\blacksquare$


Sources