Fractran
FRACTRAN is a Turing-complete esoteric programming language invented by the mathematician John Conway.
A FRACTRAN program is an ordered list of positive fractions P = (f1, f2, ... , fn), together with an initial positive integer input n.
The program is run by updating the integer n as follows:
- for the first fraction f in the list for which nf is an integer, replace n by nf ;
- repeat this rule until no fraction in the list produces an integer when multiplied by n, then halt.
Conway gave a program for primes in FRACTRAN:
- 17/91 78/85 19/51 23/38 29/33 77/29 95/23 77/19 1/17 11/13 13/11 15/14 15/2 55/1
Starting with n=2, this FRACTRAN program will change n in 15=15/2*2, then 825=55/1*15, generating the following sequence of integers:
- 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... A007542 in OEIS
After 2, this sequence contains the following powers of 2:
- 22=4, 23=8, 2^5=32, 2^7=128, 211=2048,\, 213=8192,\, 217=131072,\, 219=524288,...
which are the prime powers of 2.
More on how to program FRACTRAN as a universal programming language will be find in the references.
Your task is to write a program that reads a list of fractions as given above from the keyboard or from a string, parse it in a sequence of fractions (i.e. two integers), takes in integer and a run the above FRACTRAN. It a also asked that the number of step is limited by an internal variable easy to find.