Numbers with Integer Complexity Close to the Lower Bound

Abstract

Define $|n|$ 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 $|n|\ge 3{\log }_{3}n$ for all $n$. Define the defect of $n$, denoted $\delta (n)$, to be $|n|-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 $|2^m{3}^k|=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)={\Theta }_r((\log x{)}^{\lfloor r\rfloor +1})$, allowing us to conclude that the values of $|n|-3{\log }_{3}n$ can be arbitrarily large.

arXiv comment23 pages; to appear in INTEGERS