|
|
 |
Условие
Назовём сложностью целого числа $n$ > 1 количество сомножителей в его разложении на простые. Для каких $n$ все числа между $n$ и 2$n$ имеют сложность
а) не больше, чем у $n$;
б) меньше, чем у $n$?
Решение
Очевидно, $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$.
Ответ
а) Для $n = 2^k$; б) таких чисел нет.
Замечания
1. Для знатоков. Утверждение б) следует также из постулата Бертрана: если $p$ – простое число, то следующее простое меньше 2$p$.
Действительно, представим $n$ в виде $pr$, где $p$ простое,
$r$ натуральное. Пусть $q$ – следующее за $p$ простое число. Тогда $n < qr < 2n$, а сложность $qr$ равна сложности $n$.
2. Баллы: 2 + 2.
