Upper and lower estimates for integer complexity

Sergei Konyagin, Kristina Oganesyan

Let $\Vert n\Vert$ stand for the integer complexity of the number $n$, i.e. for the least number of $1$'s needed to write $n$ using arbitrary many additions, multiplications, and parenthe…