Сложность целых чисел: разложение на простые множители

  Очевидно, $2^k$ – наименьшее число сложности $k$.   а) Поэтому все числа между $2^k$ и $2^{k+1}$ имеют сложность не больше $k$.   Пусть $n$ – не степень двойки. Тогда между $n$ и 2$n$ есть степень двойки (можно взять наибольшую степень двойки, меньшую  n , и удвоить её). Очевидно, её сложность больше, чем у $n$.   б) В силу пункта а) достаточно рассмотреть случай  $n = 2^k$,  где $k$ натуральное. Но число $3\cdot 2^{k-1}$ имеет такую же сложность, как и $n$, и находится между $n$ и 2$n$.