user
**FRACTRAN** is a Turing-complete esoteric programming language invented by the mathematician John Horton Conway.

A FRACTRAN program is an ordered list of positive fractions 

P
=
(

f

1
,

f

2
,
…
,

f

m
)
{\displaystyle {\displaystyle P=(f\_{1},f\_{2},\ldots ,f\_{m})}}
, together with an initial positive integer input 

n
{\displaystyle {\displaystyle n}}
.

The program is run by updating the integer 

n
{\displaystyle {\displaystyle n}}
 as follows:

* for the first fraction, 

  f

  i
  {\displaystyle {\displaystyle f\_{i}}}
  , in the list for which 

  n

  f

  i
  {\displaystyle {\displaystyle nf\_{i}}}
   is an integer, replace 

  n
  {\displaystyle {\displaystyle n}}
   with 

  n

  f

  i
  {\displaystyle {\displaystyle nf\_{i}}}
   ;
* repeat this rule until no fraction in the list produces an integer when multiplied by 

  n
  {\displaystyle {\displaystyle n}}
  , then halt.

Conway gave a program for primes in FRACTRAN:

:   17

    /
    91
    {\displaystyle {\displaystyle 17/91}}
    , 

    78

    /
    85
    {\displaystyle {\displaystyle 78/85}}
    , 

    19

    /
    51
    {\displaystyle {\displaystyle 19/51}}
    , 

    23

    /
    38
    {\displaystyle {\displaystyle 23/38}}
    , 

    29

    /
    33
    {\displaystyle {\displaystyle 29/33}}
    , 

    77

    /
    29
    {\displaystyle {\displaystyle 77/29}}
    , 

    95

    /
    23
    {\displaystyle {\displaystyle 95/23}}
    , 

    77

    /
    19
    {\displaystyle {\displaystyle 77/19}}
    , 

    1

    /
    17
    {\displaystyle {\displaystyle 1/17}}
    , 

    11

    /
    13
    {\displaystyle {\displaystyle 11/13}}
    , 

    13

    /
    11
    {\displaystyle {\displaystyle 13/11}}
    , 

    15

    /
    14
    {\displaystyle {\displaystyle 15/14}}
    , 

    15

    /
    2
    {\displaystyle {\displaystyle 15/2}}
    , 

    55

    /
    1
    {\displaystyle {\displaystyle 55/1}}

Starting with 

n
=
2
{\displaystyle {\displaystyle n=2}}
, this FRACTRAN program will change 

n
{\displaystyle {\displaystyle n}}
 to 

15
=
2
×
(
15

/
2
)
{\displaystyle {\displaystyle 15=2\times (15/2)}}
, then 

825
=
15
×
(
55

/
1
)
{\displaystyle {\displaystyle 825=15\times (55/1)}}
, generating the following sequence of integers:

:   2
    {\displaystyle {\displaystyle 2}}
    , 

    15
    {\displaystyle {\displaystyle 15}}
    , 

    825
    {\displaystyle {\displaystyle 825}}
    , 

    725
    {\displaystyle {\displaystyle 725}}
    , 

    1925
    {\displaystyle {\displaystyle 1925}}
    , 

    2275
    {\displaystyle {\displaystyle 2275}}
    , 

    425
    {\displaystyle {\displaystyle 425}}
    , 

    390
    {\displaystyle {\displaystyle 390}}
    , 

    330
    {\displaystyle {\displaystyle 330}}
    , 

    290
    {\displaystyle {\displaystyle 290}}
    , 

    770
    {\displaystyle {\displaystyle 770}}
    , 

    …
    {\displaystyle {\displaystyle \ldots }}

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

:   2

    2
    =
    4
    {\displaystyle {\displaystyle 2^{2}=4}}
    , 

    2

    3
    =
    8
    {\displaystyle {\displaystyle 2^{3}=8}}
    , 

    2

    5
    =
    32
    {\displaystyle {\displaystyle 2^{5}=32}}
    , 

    2

    7
    =
    128
    {\displaystyle {\displaystyle 2^{7}=128}}
    , 

    2

    11
    =
    2048
    {\displaystyle {\displaystyle 2^{11}=2048}}
    , 

    2

    13
    =
    8192
    {\displaystyle {\displaystyle 2^{13}=8192}}
    , 

    2

    17
    =
    131072
    {\displaystyle {\displaystyle 2^{17}=131072}}
    , 

    2

    19
    =
    524288
    {\displaystyle {\displaystyle 2^{19}=524288}}
    , 

    …
    {\displaystyle {\displaystyle \ldots }}

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.

* Number Pathology: Fractran by Mark C. Chu-Carroll; October 27, 2006.
assistant
(formerly Perl 6)

**Works with**: rakudo version 2015-11-03

A Fractran program potentially returns an infinite list, and infinite lists are a common data structure in Raku. The limit is therefore enforced only by slicing the infinite list.

```
sub fractran(@program) {
    2, { first Int, map (* * $_).narrow, @program } ... 0
}
say 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>)[^100];

```

Output:

```
(2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132 116 308 364 68 4 30 225 12375 10875 28875 25375 67375 79625 14875 13650 2550 2340 1980 1740 4620 4060 10780 12740 2380 2184 408 152 92 380 230 950 575 2375 9625 11375 2125 1950 1650 1450 3850 4550 850 780 660 580 1540 1820 340 312 264 232 616 728 136 8 60 450 3375 185625 163125 433125 380625 1010625 888125 2358125 2786875 520625 477750 89250 81900 15300 14040 11880 10440 27720 24360 64680 56840 150920 178360 33320 30576 5712 2128 1288)
```

**Extra credit:**
We can weed out all the powers of two into another infinite constant list based on the first list. In this case the sequence is limited only by our patience, and a ^C from the terminal. The .msb method finds the most significant bit of an integer, which conveniently is the base-2 log of the power-of-two in question.

```
sub fractran(@program) {
    2, { first Int, map (* * $_).narrow, @program } ... 0
}
for 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> {
        say $++, "\t", .msb, "\t", $_ if 1 +< .msb == $_;
}

```

Output:

```
0       1       2
1	2	4
2	3	8
3	5	32
4	7	128
5	11	2048
6	13	8192
7	17	131072
8	19	524288
9	23	8388608
^C
```