Smallest Integer not Sum of Two Ulam Numbers

From ProofWiki
Jump to navigation Jump to search

Theorem

The smallest integer greater than $1$ which is not the sum of two Ulam numbers is $23$.


Proof

Recall the Ulam numbers:

The sequence of Ulam numbers begins as follows:

$1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, \ldots{}$


We have:

\(\displaystyle 2\) \(=\) \(\displaystyle 1 + 1\)
\(\displaystyle 3\) \(=\) \(\displaystyle 2 + 1\)
\(\displaystyle 4\) \(=\) \(\displaystyle 3 + 1\)
\(\displaystyle \) \(=\) \(\displaystyle 2 + 2\)
\(\displaystyle 5\) \(=\) \(\displaystyle 4 + 1\)
\(\displaystyle \) \(=\) \(\displaystyle 3 + 2\)
\(\displaystyle 6\) \(=\) \(\displaystyle 4 + 2\)
\(\displaystyle \) \(=\) \(\displaystyle 3 + 3\)
\(\displaystyle 7\) \(=\) \(\displaystyle 6 + 1\)
\(\displaystyle \) \(=\) \(\displaystyle 4 + 3\)
\(\displaystyle 8\) \(=\) \(\displaystyle 6 + 2\)
\(\displaystyle \) \(=\) \(\displaystyle 4 + 4\)
\(\displaystyle 9\) \(=\) \(\displaystyle 8 + 1\)
\(\displaystyle \) \(=\) \(\displaystyle 6 + 3\)
\(\displaystyle 10\) \(=\) \(\displaystyle 8 + 2\)
\(\displaystyle \) \(=\) \(\displaystyle 6 + 4\)
\(\displaystyle 11\) \(=\) \(\displaystyle 8 + 3\)
\(\displaystyle 12\) \(=\) \(\displaystyle 11 + 1\)
\(\displaystyle \) \(=\) \(\displaystyle 8 + 4\)
\(\displaystyle \) \(=\) \(\displaystyle 6 + 6\)
\(\displaystyle 13\) \(=\) \(\displaystyle 11 + 2\)
\(\displaystyle 14\) \(=\) \(\displaystyle 13 + 1\)
\(\displaystyle \) \(=\) \(\displaystyle 11 + 3\)
\(\displaystyle \) \(=\) \(\displaystyle 8 + 6\)
\(\displaystyle 15\) \(=\) \(\displaystyle 13 + 2\)
\(\displaystyle \) \(=\) \(\displaystyle 11 + 4\)
\(\displaystyle 16\) \(=\) \(\displaystyle 13 + 3\)
\(\displaystyle \) \(=\) \(\displaystyle 8 + 8\)
\(\displaystyle 17\) \(=\) \(\displaystyle 16 + 1\)
\(\displaystyle \) \(=\) \(\displaystyle 13 + 4\)
\(\displaystyle \) \(=\) \(\displaystyle 11 + 6\)
\(\displaystyle 18\) \(=\) \(\displaystyle 16 + 2\)
\(\displaystyle 19\) \(=\) \(\displaystyle 18 + 1\)
\(\displaystyle \) \(=\) \(\displaystyle 16 + 3\)
\(\displaystyle \) \(=\) \(\displaystyle 13 + 6\)
\(\displaystyle \) \(=\) \(\displaystyle 11 + 8\)
\(\displaystyle 20\) \(=\) \(\displaystyle 18 + 2\)
\(\displaystyle \) \(=\) \(\displaystyle 16 + 4\)
\(\displaystyle 21\) \(=\) \(\displaystyle 18 + 3\)
\(\displaystyle \) \(=\) \(\displaystyle 13 + 8\)
\(\displaystyle 22\) \(=\) \(\displaystyle 18 + 4\)
\(\displaystyle \) \(=\) \(\displaystyle 16 + 6\)
\(\displaystyle \) \(=\) \(\displaystyle 11 + 11\)


Now consider the the difference between $23$ and successive Ulam numbers:

\(\displaystyle 23 - 18\) \(=\) \(\displaystyle 5\) not a Ulam number
\(\displaystyle 23 - 16\) \(=\) \(\displaystyle 7\) not a Ulam number
\(\displaystyle 23 - 13\) \(=\) \(\displaystyle 10\) not a Ulam number
\(\displaystyle 23 - 11\) \(=\) \(\displaystyle 12\) not a Ulam number

and it is not necessary to go further back.


Hence the result.

$\blacksquare$


Sources