Решение задачи 492

Условие:

Докажите, что найдутся миллион идущих подряд натуральных чисел, среди которых ровно тысяча простых.

Решение:

Среди первых миллион натуральных чисел простых больше тысячи (можно посмотреть таблицу). Покажем, что для любого натурального N найдутся N подряд идущих составных чисел. Через А обозначим (N+1)!+2. Следующие N чисел являются составными: A, A + 1, ..., A + (N−1). Значит, найдутся миллион подряд идущих составных чисел.

Возьмем отрезок из первых миллион чисел и будем сдвигать его пошагово вправо. Будем следить за величиной "количество простых чисел в отрезке". При сдвиге отрезка на одно число эта величина либо не меняется, либо увеличивается на единицу, либо уменьшается на единицу.

Изначально величина больше тысячи, в какой-то момент она равна нулю, а так как с шагом она изменяется не больше, чем на единицу, то в какой-то промежуточный момент она равна тысяче.