|
|
 |
Условие
С натуральным числом K производится следующая операция: оно представляется в виде произведения простых сомножителей K = p1p2...pn; затем вычисляется сумма p1 + p2 + ... + pn + 1. С полученным числом производится то же самое, и т.д.
Доказать, что образующаяся последовательность, начиная с некоторого номера, будет периодической.
Решение
Обозначим через f(K) сумму p1 + p2 + ... + pn + 1. Простым подсчётом проверим, что если K > 9, то последовательность с какого-нибудь момента станет периодической.
Лемма. Пусть либо a > 2, b ≥ 3, либо a ≥ 2, b > 3, тогда ab > a + b + 1.
Доказательство. Запишем неравенство в виде (a – 1)(b – 1) > 2. Теперь оно очевидно.
Заметим, что если K является степенью двойки, причём K > 8, то f(K) < K. Таким образом, если K = p1p2...pn и K ≥ 9 не простое, то f(K) < K. Если же K простое, то f(K) = K + 1 не простое, а значит, f(f(K)) < K + 1. Тогда либо f(f (K)) = K (при этом последовательность периодическая), либо f(f (K)) < K. Теперь несложно доказать по индукции, что для любого K последовательность периодическая.
