'''[[wp:FRACTRAN|FRACTRAN]]''' is a Turing-complete esoteric programming language invented by the mathematician [[wp:John Horton Conway|John Horton Conway]].

A FRACTRAN program is an ordered list of positive fractions <math>P = (f_1, f_2, \ldots, f_m)</math>, together with an initial positive integer input <math>n</math>.


The program is run by updating the integer <math>n</math> as follows:

* for the first fraction, <math>f_i</math>, in the list for which <math>nf_i</math> is an integer, replace <math>n</math> with <math>nf_i</math> ;
* repeat this rule until no fraction in the list produces an integer when multiplied by <math>n</math>, then halt.

<br>
Conway gave a program for primes in FRACTRAN:

: <math>17/91</math>, <math>78/85</math>, <math>19/51</math>, <math>23/38</math>, <math>29/33</math>, <math>77/29</math>, <math>95/23</math>, <math>77/19</math>, <math>1/17</math>, <math>11/13</math>, <math>13/11</math>, <math>15/14</math>, <math>15/2</math>, <math>55/1</math>

Starting with <math>n=2</math>, this FRACTRAN program will change <math>n</math> to <math>15=2\times (15/2)</math>, then <math>825=15\times (55/1)</math>, generating the following sequence of integers:

: <math>2</math>, <math>15</math>, <math>825</math>, <math>725</math>, <math>1925</math>, <math>2275</math>, <math>425</math>, <math>390</math>, <math>330</math>, <math>290</math>, <math>770</math>, <math>\ldots</math>

After 2, this sequence contains the following powers of 2:

:<math>2^2=4</math>, <math>2^3=8</math>, <math>2^5=32</math>, <math>2^7=128</math>, <math>2^{11}=2048</math>, <math>2^{13}=8192</math>, <math>2^{17}=131072</math>, <math>2^{19}=524288</math>, <math>\ldots</math>

which are the prime powers of 2.


;Task:
Write a program that reads a list of fractions in a ''natural'' format from the keyboard or from a string,
to parse it into a sequence of fractions (''i.e.'' two integers),
and runs the FRACTRAN starting from a provided integer, writing the result at each step.
It is also required that the number of steps is limited (by a parameter easy to find).


;Extra credit:
Use this program to derive the first '''20''' or so prime numbers.


;See also:
For more on how to program FRACTRAN as a universal programming language, see:
* J. H. Conway (1987). Fractran: A Simple Universal Programming Language for Arithmetic. In: Open Problems in Communication and Computation, pages 4–26. Springer.

* J. H. Conway (2010). "FRACTRAN: A simple universal programming language for arithmetic". In Jeffrey C. Lagarias. The Ultimate Challenge: the 3x+1 problem. American Mathematical Society. pp. 249–264. ISBN 978-0-8218-4940-8. Zbl 1216.68068.

* [http://scienceblogs.com/goodmath/2006/10/27/prime-number-pathology-fractra/Prime Number Pathology: Fractran] by  Mark C. Chu-Carroll; October 27, 2006.
<br><br>