Английский математик Джон Хортон Конвей изобрел множество математических развлечений, доставляющих не только удовольствие, но и пищу для серьезных размышлений. Одно из его изобретений – язык программирования FRACTRAN, о котором пойдет речь в данной задаче.

Память данных виртуальной машины языка FRACTRAN содержит одно единственное целое число, а программа представляет собой упорядоченную последовательность рациональных дробей. На каждом шаге выполнения программы машина просматривает эти дроби одну за другой слева направо и умножает каждую из них на число из памяти, пока произведение не окажется целым. Полученное целое число записывают в память вместо предыдущего. 

Вот, например, FRACTRAN-программа, предложенная Конвеем для получения последовательности простых чисел:

17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/2, 1/7, 55/1.

Записав в память исходное значение 2, получим в памяти ряд чисел в следующей последовательности:

15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4, 30, ..., 136, 8, 60, ..., 544, 32, 240, ...

Оказывается, степени двойки в полученной последовательности встречаются только с простыми показателями: 2², 2³, 2⁵, ..., и можно проверить, что данная последовательность будет содержать в порядке возрастания все степени двух с простыми показателями.

Заметим, что для получения 2² из исходного числа 2 потребовалось 19 шагов программы, и при этом три раза происходило умножение на дробь 13/11.

А сколько раз придется выполнить умножение на 13/11 при переходе от исходного числа 2 к 2¹¹¹¹¹⁹?