Question

Мистер Фокс сделал любопытный автомат: если в него засунуть карточку с числом M, то автомат выдаст такую же карточку, но с числом M+d, где d -— наибольший натуральный делитель числа M, отличный от M. Полученную карточку можно снова засовывать в автомат. Мистер Фокс выбрал число M, которое делится на 2, но не делится на 4, и сунул карточку с этим числом в автомат. Полученную карточку он снова сунул в автомат, и так далее. Когда Мистер Фокс устал, у него была карточка с число 3 в 500 степени ⋅M. Сколько операций сделал мистер Фокс со своим чудесным автоматом?

Answer 1

Первоначально число М = 2d, т.к. число делится на 2, а наибольший делитель равен d

посмотрим как меняется число:

первая операция: 2d + d = 3d - снова наибольший делитель d, т.к. d не делится на 2

вторая операция: 3d + d = 4d - наибольший делитель 2d

третья операция: 4d + 2d = 6d - наибольший делитель 3d

четвертая операция: 6d + 3d = 9d - наибольший делитель 3d

пятая операция: 9d + 3d = 12d - наибольший делитель 6d

шестая операция: 12d + 6d = 18d - наибольший делитель 9d

седьмая операция 18d + 9d = 27d - наибольший делитель 9d

заметим, что каждая 3n-ая операция образует число 3ⁿ*2d = 3ⁿ*M

при n = 500 получим нужное число операций:

3 * n = 3 * 500 = 1500

Ответ: 1500 операций

Answer 2

Чтобы решить эту задачу, нужно определить количество операций, которые Мистер Фокс совершил с автоматом, чтобы получить карточку с числом 3 в 500 степени ⋅ M.

Поскольку карточка с числом M была засунута в автомат несколько раз, и каждый раз она увеличивалась на наибольший натуральный делитель числа M, отличный от M, можно предположить, что каждый раз она увеличивалась на простое число.

Таким образом, мы можем представить число M в виде произведения простых чисел. Поскольку M делится на 2 и не делится на 4, можно представить M в виде M = 2^k * p, где k ≥ 2, а p - нечетное простое число.

Для получения числа 3 в 500 степени ⋅ M, карточка должна была пройти через 500 операций, каждая из которых увеличивала бы число на простое число. Так как число 3^500 содержит только одно простое число в своем разложении (3), остальные множители равны 1, в каждой операции Мистер Фокс добавлял только число 3.

Следовательно, Мистер Фокс совершил 500 операций с автоматом.