2022/11/06 by Zelinsky, Joshua
#FOS: Mathematics #Number Theory (math.NT)
paper · doi:10.48550/arxiv.2211.02995
Define ||n|| to be the complexity of n, which is the smallest number of 1s needed to write n using an arbitrary combination of addition and multiplication. John Selfridge showed that ||n|| ≥ 3log3 n for all n. Richard Guy noted the trivial upper bound that ||n|| ≤ 3log2 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|| ≤ A log n where A = (41)/(log 55296).