Integer Complexity: Breaking the θ(n2) barrier

E-print/Working paper (2008)

The \textit{integer complexity} of a positive integer $n$, denoted $f(n)$, is defined as the least number of 1's required to represent $n$, using only 1's, the addition and multiplication operators, and ... [more ▼]

The \textit{integer complexity} of a positive integer $n$, denoted $f(n)$, is defined as the least number of 1's required to represent $n$, using only 1's, the addition and multiplication operators, and the parentheses. The running time of the algorithm currently used to compute $f(n)$ is $\Theta(n^{2})$. In this paper we present an algorithm with $\Theta(n^{\log_{2}3})$ as its running time. We also present a proof of the theorem: the largest solutions of $f(m)=3k,\,3k\pm1$ are, respectively, $m=3^{k},\,3^{k}\pm3^{k-1}$. [less ▲]