Numbers with Integer Complexity Close to the Lower Bound

Define $\mathrm{\mid }n\mathrm{\mid }$ to be the complexity of $n$, the smallest number of 1’s needed to write $n$ using an arbitrary combination of addition and multiplication. John Selfridge showed that $\mathrm{\mid }n\mathrm{\mid }\ge 3{\log }_{3}n$ for all $n$. Define the defect of $n$, denoted $\delta (n)$, to be $\mathrm{\mid }n\mathrm{\mid }-3{\log }_{3}n$; in this paper we present a method for classifying all $n$ with $\delta (n)<r$ for a given $r$. From this, we derive several consequences. We prove that $\mathrm{\mid }{2}^m{3}^k\mathrm{\mid }=2m+3k$ for $m\le 21$ with $m$ and $k$ not both zero, and present a method that can, with more computation, potentially prove the same for larger $m$. Furthermore, defining $A_r(x)$ to be the number of $n$ with $\delta (n)<r$ and $n\le x$, we prove that $A_r(x)={\mathrm{\Theta }}_r((\log x{)}^{\lfloor r\rfloor +1})$, allowing us to conclude that the values of $\mathrm{\mid }n\mathrm{\mid }-3{\log }_{3}n$ can be arbitrarily large.