Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:
1. Если исходное число кратно 2, оно делится на 2, в противном случае из него вычитается 1.
2. Если полученное на предыдущем шаге число кратно 3, оно делится на 3, в противном случае из него вычитается 1.
3. Если полученное на предыдущем шаге число кратно 5, оно делится на 5, в противном случае из него вычитается 1.
4. Число, полученное на шаге 3, считается результатом работы алгоритма.
Пример. Дано число N = 22. Алгоритм работает следующим образом:
1. Число 22 кратно 2, оно делится на 2, получается 11.
2. Число 11 не кратно 3, из него вычитается 1, получается 10.
3. Число 10 кратно 5, оно делится на 5, получается 2.
4. Результат работы алгоритма R = 2.
Сколько существует различных натуральных чисел N, при обработке которых получится R = 1?
Рассмотрим работу алгоритма в обратном порядке:
Красным на рисунке отмечены пути, которые не подходят по условию задачи. Число 2 нельзя получить вычитанием единицы из числа 3, поскольку оно кратно трём. Число 5 нельзя получить вычитанием единицы из числа 6, поскольку оно кратно трём. Число 15 нельзя получить вычитанием единицы из числа 16, поскольку оно кратно двум.
Таким образом, подходят три числа: 7, 12 и 30.
Ответ: 3.
Приведем решение Михаила Глинского.
Заметим, что исходное число не превышает 30, поскольку из больших чисел при последовательном делении на 2, 3 и 5 получатся числа, большие 1. С помощью программы на языке Паскаль будем перебирать числа от 1 до 30, обрабатывать их по заданному алгоритму и выводить на экран, если в результате обработки получится 1.
var
i,x:integer;
begin
for i:=1 to 30 do begin
x:=i;
if x mod 2=0 then x:= x div 2 else x:=x-1;
if x mod 3=0 then x:= x div 3 else x:=x-1;
if x mod 5=0 then x:= x div 5 else x:=x-1;
if x=1 then println(i);
end;
end.