Question

Назовем 13-значное число особенным, если его нельзя разложить в произведение двух 7-значных чисел. Какое наибольшее количество особенных чисел может идти подряд?

Answer 1

Шесть: 15,16,17,18,19,20

Answer 2

Заметим, что любое 13-значное число можно разложить на произведение двух чисел: первое из которых содержит первые 7 цифр, а второе - последние 6 цифр. Таким образом, чтобы число было особенным, его первые 7 цифр и последние 6 цифр должны не иметь нетривиальных общих делителей.

Воспользуемся теоремой о числах, взаимно простых в совокупности: два числа взаимно просты, если и только если их наибольший общий делитель равен 1. Таким образом, чтобы 13-значное число было особенным, его первые 7 цифр и последние 6 цифр должны быть взаимно простыми.

Количество 7-значных чисел, взаимно простых с заданным 7-значным числом, равно количеству 7-значных чисел, у которых есть общих делителей с заданным числом не более чем до 6-значных чисел. Поскольку простых чисел среди 6-значных всего 487, а каждое 7-значное число делится на некоторое простое число из этого множества, то количество 7-значных чисел, не взаимно простых с заданным числом, не превышает $487^2$.

Таким образом, количество особенных чисел, которые могут идти подряд, не может превышать количества 7-значных чисел, не взаимно простых с любым 7-значным числом, т.е. $10^7 - 487^2 \approx 9.51 \cdot 10^6$. Значит, наибольшее количество особенных чисел, которые могут идти подряд, равно $\boxed{9\ 510\ 000}$.