Upper Bounds on Integer Complexity

Abstract

Define $||n||$ to be the \emph{complexity} of $n$, which is 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$. Richard Guy noted the trivial upper bound that $||n||\le 3{\log }_{2}n$ for all $n>1$ by writing $n$ in base 2. An upper bound for almost all $n$ was provided by Juan Arias de Reyna and Jan Van de Lune. This paper provides the first non-trivial upper bound for all $n$. In particular, for all $n>1$ we have $||n||\le A\log n$ where $A=\frac{41}{\log 55296}$.

52 pages