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:
$$\dfrac{17}{91}, \dfrac{78}{85}, \dfrac{19}{51}, \dfrac{23}{38}, \dfrac{29}{33}, \dfrac{77}{29}, \dfrac{95}{23}, \dfrac{77}{19}, \dfrac{1}{17}, \dfrac{11}{13}, \dfrac{13}{11}, \dfrac{15}{2}, \dfrac{1}{7}, \dfrac{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 ?

Firstly, it must be noted that Fractran is effectively a Turing-complete language. This means that it is capable of solving complex computations including identifying primes.

Conway’s prime generating Fractran program works as follow. It starts with the seed integer and multiplies it by the first fraction that leaves the result as an integer. For example, starting with the seed of 2, the first fraction that makes the result an integer is 15/2, which yields 15 as the new state. The process is then repeated for this new number.

However, the program doesn’t directly output prime numbers. Instead, it produces powers of 2 (2^n) where n is a prime number.

This means that to find the nth prime number (for example, the 10001st prime for Project Euler Problem 7), you would have to iterate through the Fractran program until it produces 2^n where n is the nth prime number.

The speed of Fractran is not typically measured in terms of iterations as the concept of an iteration is not clearly defined or uniform across all programs and inputs. Thus, to predict precisely how many iterations the program needed to produce 2^10001, we’d have to run the program. Remember, the index of the power of two listed above gets incremented each time a new power of 2 appears. Therefore, the index of 2^10001 in that sequence is actually the 10001st prime, which is what you would have to iterate the program to find.

Given that most programming languages have built-in functions for prime computation that are more efficient, Fractran is not a practical method for computing large primes in any reasonable time frame. Thus, although theoretically possible, using Fractran to compute the 10001st prime for Project Euler Problem 7 may not be practically feasible or efficient.

The number of iterations it would take to compute the 10001st prime would most likely be extremely large, given that simple programs in Fractran can require billions of iterations to compute relatively simple functions. Furthermore, each successive prime requires exponentially more iterations.

Hence, while it’s a fascinating language from a theoretical and mathematical perspective, Fractran isn’t typically used for solving problems that require producing prime numbers of this magnitude. For this reason, a precise number of iterations required to solve Project Euler Problem 7 using Conway’s Fractran program cannot be reasonably estimated without actually running the program.

More Answers: