а) Оче­вид­но,   — наи­мень­шее число слож­но­сти k. По­это­му все числа между и имеют слож­ность не боль­ше k. Пусть n  — не сте­пень двой­ки. Тогда между n и есть сте­пень двой­ки (можно взять наи­боль­шую сте­пень двой­ки, мень­шую n, и удво­ить её). Оче­вид­но, её слож­ность боль­ше, чем у

б) В силу пунк­та а), до­ста­точ­но рас­смот­реть слу­чай где k на­ту­раль­ное. Но число имеет такую же слож­ность, как и n, и на­хо­дит­ся между n и

Для зна­то­ков. Утвер­жде­ние б) сле­ду­ет из по­сту­ла­та Бер­тра­на: если p  — про­стое число, то сле­ду­ю­щее про­стое мень­ше 2p. Дей­стви­тель­но, пред­ста­вим n в виде pr, где p  — про­стое, r  — на­ту­раль­ное. Пусть q  — сле­ду­ю­щее за p про­стое число. Тогда а слож­ность qr равна слож­но­сти n.

Ответ: а) Для б) таких чисел нет.