Степени вхождения простых

Лемма. Число является удачным тогда и только тогда, когда каждое простое число входит в разложение на простые множители с одним из следующих показателей:

Доказательство. Назовем целое неотрицательное число счастливым, если не существует такого целого что Заметим, что счастливыми являются в точности числа При в этом можно убедиться прямой проверкой. Если же то выберем такое максимальное число что Тогда и по выбору то есть несчастливо.

Пусть число неудачно, то есть делится на но не делится на для некоторого Тогда некоторое простое входит в разложение в меньшей степени, чем в разложение Пусть входит в разложения и в степенях и соответственно; тогда но Значит, число — несчастливое. Итак, если все степени вхождения простых чисел в счастливы, то удачно.

Если же где не кратно и несчастливо то при число делится на а не делится на то есть неудачно.

Согласно лемме, каждое неудачное число имеет простой делитель, входящий в разложение на простые множители с показателем или более Поскольку и каждое неудачное число, меньшее принадлежит одному из следующих непересекающихся классов:

Числа вида где нечётно и

Числа вида где нечётно и

Числа вида где или

Число

Числа вида где не кратно и

Таким образом, общее количество неудачных чисел, меньших равно а количество удачных чисел равно