Question

Мистер Фокс сделал любопытный автомат: если в него засунуть карточку с числом M , то автомат выдаст такую же карточку, но с числом M+d, где d-наибольший натуральный делитель числа M , отличный от M. Полученную карточку можно снова засовывать в автомат. Мистер Фокс выбрал число , которое делится на 2, но не делится на 4, и сунул карточку с этим числом в автомат. Полученную карточку он снова сунул в автомат, и так далее. Когда Мистер Фокс устал, у него была карточка с число 3 в 300 степени .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 = 300 получим нужное число операций:

3 * n = 3 * 300 = 900

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

Answer 2

Давайте разберем эту задачу шаг за шагом:

1. Мистер Фокс выбрал число, которое делится на 2, но не делится на 4. Это означает, что его число M - четное, но не кратно 4.

2. Каждый раз, когда Мистер Фокс засовывает карточку с числом M в автомат, автомат выдаст карточку с числом M+d, где d - наибольший натуральный делитель числа M, отличный от M.

3. Число M = 2^n, где n - некоторое натуральное число, потому что M - степень 2. Из условия также известно, что M не делится на 4. Таким образом, M = 2^1, 2^2, 2^3, ... и т.д., но не M = 2^2, 2^4, 2^6, ... и т.д.

4. Наибольший натуральный делитель числа M, отличный от M, будет M/2, так как M делится на 2 и не делится на большее число.

Теперь рассмотрим несколько итераций:

1. Итерация 1: M = 2^1, d = M/2 = 2^1/2 = 2^0 = 1. Полученная карточка будет с числом M+d = 2^1 + 2^0 = 2 + 1 = 3.

2. Итерация 2: M = 3, d = M/2 = 3/2. Так как d не является натуральным числом, Мистер Фокс закончил операции, так как число 3 нечетное и больше его нельзя делить на 2 без остатка.

Таким образом, Мистер Фокс сделал всего 1 операцию со своим чудесным автоматом.