Integer complexity: algorithms and computational results

Harry Altman

Published 2016-06-11Version 1

Define $\|n\|$ to be the complexity of $n$, the smallest number of ones needed to write $n$ using an arbitrary combination of addition and multiplication. Define $n$ to be stable if for all $k\ge 0$, we have $\|3^k n\|=\|n\|+3k$. In [7], this author and Zelinsky showed that for any $n$, there exists some $K=K(n)$ such that $3^K n$ is stable; however, the proof there provided no upper bound on $K(n)$ or any way of computing it. In this paper, we describe an algorithm for computing $K(n)$, and thereby also show that the set of stable numbers is a computable set. The algorithm is based on considering the defect of a number, defined by $\delta(n):=\|n\|-3\log_3 n$, building on the methods presented in [3]. As a side benefit, this algorithm also happens to allow fast evaluation of the complexities of powers of $2$; we use it to verify that $\|2^k 3^\ell\|=2k+3\ell$ for $k\le48$ and arbitrary $\ell$ (excluding the case $k=\ell=0$), providing more evidence for the conjecture that $\|2^k 3^\ell\|=2k+3\ell$ whenever $k$ and $\ell$ are not both zero. An implementation of these algorithms in Haskell is available.