Задача 308
Удивительный автомат для генерации простых чисел

Программа, написанная на языке программирования Fractran, состоит из списка дробей.

Внутреннее состояние виртуальной машины Fractran — это положительное целое число, которое изначально устанавливается равным начальному числу генератора (seed value). При каждой итерации Fractran-программы число состояния машины умножается на первую дробь в списке, которая даст в результате целое число.

Например, одна из программ на Fractran, написанная Джоном Хортоном Конвейем для генерации простых чисел, состоит из следующих 14 дробей:

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, ..., 68, 4, 30, ..., 136, 8, 60, ..., 544, 32, 240, ...

В этой последовательности появляются следующие степени двойки: 2^(2), 2^(3), 2^(5), ...
Можно показать, что все степени двойки в этой последовательности имеют простые показатели и, кроме того, все простые числа в показателях степеней двойки появляются в правильном порядке.

Если использовать приведённую выше программу на Fractran при решении 7-й задачи проекта «Эйлер» (найдите 10001-ое простое число), то сколько итераций потребуется, прежде чем программа выдаст число 2^(10001-ое простое число)?

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net