Integer Complexity and Well-Ordering

Define $\mathrm{\parallel }n\mathrm{\parallel }$ to be the complexity of $n$, the smallest number of ones needed to write $n$ using an arbitrary combination of addition and multiplication. John Selfridge showed that $\mathrm{\parallel }n\mathrm{\parallel }\ge 3{\log }_{3}n$ for all $n$. Define the defect of $n$, denoted $\delta (n)$, to be $\mathrm{\parallel }n\mathrm{\parallel }-3{\log }_{3}n$. In this paper, we consider the set $\mathcal{D}:=\{\delta (n):n\ge 1\}$ of all defects. We show that as a subset of the real numbers, the set $\mathcal{D}$ is well-ordered, of order type ${\omega }^{\omega }$. More specifically, for $k\ge 1$ an integer, $\mathcal{D}\cap [0,k)$ has order type ${\omega }^k$. We also consider some other sets related to $\mathcal{D}$, and show that these too are well-ordered and have order type ${\omega }^{\omega }$.