У исполнителя Квадратор две команды, которым присвоены номера:
1. прибавь 2,
2. возведи в квадрат.
Первая из этих команд увеличивает число на экране на 2, а вторая — возводит его в квадрат. Программа исполнителя Квадратор — это последовательность номеров команд. Например, 12211 — это программа
прибавь 2
возведи в квадрат
возведи в квадрат
прибавь 2
прибавь 2
Эта программа преобразует, например, число 1 в число 85.
Запишите программу, которая преобразует число 1 в число 123 и содержит не более 5 команд. Если таких программ более одной, запишите любую из них.
Не любое число является квадратом целого числа, поэтому, если мы пойдём от числа 123 к числу 1, тогда однозначно восстановим программу. Полученные команды будут записываться справа налево.
1) Число 123 не является квадратом, значит, оно получено добавлением двух к числу 121: 123 = 121 + 2 (команда 1).
2) Число 121 является квадратом числа 11: 121 = 11·11 (команда 2).
3) Число 11 не является квадратом, поэтому оно получено добавлением двух к числу 9: 11 = 9 + 2 (команда 1).
4) Число 9 является квадратом числа 3: 9 = 3·3 (команда 2).
5) Число 3 не является квадратом, то есть оно получено прибавлением 2 к 1: 3 = 1 + 2 (команда 1).
Искомая последовательность команд: 12121.