Problem 308
An amazing Prime-generating Automaton
A program written in the programming language Fractran consists of a list of fractions.
The internal state of the Fractran Virtual Machine is a positive integer, which is initially set to a seed value. Each iteration of a Fractran program multiplies the state integer by the first fraction in the list which will leave it an integer.
For example, one of the Fractran programs that John Horton Conway wrote for prime-generation consists of the following 14 fractions:
$\frac{17}{91}$, $\frac{78}{85}$, $\frac{19}{51}$, $\frac{23}{38}$, $\frac{29}{33}$, $\frac{77}{29}$, $\frac{95}{23}$, $\frac{77}{19}$, $\frac{1}{17}$, $\frac{11}{13}$, $\frac{13}{11}$, $\frac{15}{2}$, $\frac{1}{7}$, $\frac{55}{1}$.
Starting with the seed integer 2, successive iterations of the program produce the sequence:
15, 825, 725, 1925, 2275, 425, …, 68, 4, 30, …, 136, 8, 60, …, 544, 32, 240, …
The powers of 2 that appear in this sequence are 22, 23, 25, …
It can be shown that all the powers of 2 in this sequence have prime exponents and that all the primes appear as exponents of powers of 2, in proper order!
If someone uses the above Fractran program to solve Project Euler Problem 7 (find the 10001st prime), how many iterations would be needed until the program produces 210001st prime?
神奇的素数生成自动机
用编程语言Fractran所写的程序由一个分数序列组成。
Fractran虚拟机的内部状态为一个正整数，初始化时被设定为某个种子值。在Fractran程序每次迭代时，找到序列中第一个与状态整数相乘得到整数的分数，并更新状态整数为新得到的整数。
例如，约翰·何顿·康威所写的一个用于素数生成的Fractran程序由下列14个分数组成：
$\frac{17}{91}$, $\frac{78}{85}$, $\frac{19}{51}$, $\frac{23}{38}$, $\frac{29}{33}$, $\frac{77}{29}$, $\frac{95}{23}$, $\frac{77}{19}$, $\frac{1}{17}$, $\frac{11}{13}$, $\frac{13}{11}$, $\frac{15}{2}$, $\frac{1}{7}$, $\frac{55}{1}$.
从种子值2开始，这个程序的连续迭代生成了如下的序列：
15, 825, 725, 1925, 2275, 425, …, 68, 4, 30, …, 136, 8, 60, …, 544, 32, 240, …
在这个序列中出现的2的幂为22, 23, 25, …
可以看出所有出现在序列中的2的幂，其指数均为素数，而且所有素数恰好按顺序作为2的指数出现！
如果有人用上述Fractran程序来解决欧拉计划第7题（找出第10001个素数），需要迭代多少步才能生成2第10001个素数?