ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66827
Темы:    [ Теория чисел. Делимость (прочее) ]
[ Основная теорема арифметики. Разложение на простые сомножители ]
Сложность: 3
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Назовём сложностью целого числа n > 1 количество сомножителей в его разложении на простые. Для каких n все числа между n и 2n имеют сложность
а) не больше, чем у n;
б) меньше, чем у n?

Решение

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

б) В силу пункта а), достаточно рассмотреть случай $n=2^k$, где k натуральное. Но число $3\cdot 2^{k-1}$ имеет такую же сложность, как и n, и находится между n и 2n.

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

Ответ

а) Для $n=2^k$; б) таких чисел нет.

Источники и прецеденты использования

олимпиада
Название Турнир городов
номер/год
Номер 41
Год 2019/20
вариант
Вариант осенний тур, сложный вариант, 8-9 класс
задача
Номер 1

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .