{"id":"arxiv/2603.20876","url":"https://arxiv.org/abs/2603.20876","tags":["math.NT","math.CO"],"score":0,"title":"Upper and lower estimates for integer complexity","domain":"math.NT","source":"arxiv","authors":["Sergei Konyagin","Kristina Oganesyan"],"reviews":0,"subject":"math.NT","summary":"Let $\\|n\\|$ 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 parentheses. The two-sided inequality $3\\log_3 n\\leq\\|n\\|\\leq 3\\log_2 n$ for all $n$ is well known and reveals the logarithmic behaviour of the complexity function $\\|n\\|$. While the lower bound $3\\log_3 n$ is attained infinitely many times at powers of $3$, the best upper estimate is still unknown, although there are some improvements of the trivial bound $3\\log_2 n$. Besides, for $``$typical$\"$ numbers, i.e. for almost…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-21","reactions":{}}