Fractran

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},\ldots ,f_{m})$ , together with an initial positive integer input $n$ .

The program is run by updating the integer $n$ as follows:

for the first fraction, $f_{i}$ , in the list for which $nf_{i}$ is an integer, replace $n$ with $nf_{i}$ ;
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$ to $15=2\times (15/2)$ , then $825=15\times (55/1)$ , generating the following sequence of integers:

2

,

15

,

825

,

725

,

1925

,

2275

,

425

,

390

,

330

,

290

,

770

,

\ldots

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

2^{2}=4

,

2^{3}=8

,

2^{5}=32

,

2^{7}=128

,

2^{11}=2048

,

2^{13}=8192

,

2^{17}=131072

,

2^{19}=524288

,

\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.

11l

Translation of: D

F fractran(prog, =val, limit)
   V fracts = prog.split(‘ ’).map(p -> p.split(‘/’).map(i -> Int(i)))
   [Float] r
   L(n) 0 .< limit
      r [+]= val
      L(p) fracts
         I val % p[1] == 0
            val = p[0] * val / p[1]
            L.break
   R r

print(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’, 2, 15))

Output:

[2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132]

360 Assembly

*        FRACTRAN                  17/02/2019
FRACTRAN CSECT
         USING  FRACTRAN,R13       base register
         B      72(R15)            skip savearea
         DC     17F'0'             savearea
         SAVE   (14,12)            save previous context
         ST     R13,4(R15)         link backward
         ST     R15,8(R13)         link forward
         LR     R13,R15            set addressability
         LA     R6,1               i=1
       DO WHILE=(C,R6,LE,TERMS)    do i=1 to terms
         LA     R7,1                 j=1
       DO WHILE=(C,R7,LE,=A(NF))     do j=1 to nfracs
         LR     R1,R7                  j
         SLA    R1,3                   ~
         L      R2,FRACS-4(R1)         d(j)
         L      R4,NN                  nn
         SRDA   R4,32                  ~
         DR     R4,R2                  nn/d(j)
       IF       LTR,R4,Z,R4 THEN       if mod(nn,d(j))=0 then
         XDECO  R6,XDEC                  edit i
         MVC    PG(3),XDEC+9             output i
         L      R1,NN                    nn
         XDECO  R1,PG+5                  edit & output nn
         XPRNT  PG,L'PG                  print buffer
         LR     R1,R7                    j
         SLA    R1,3                     ~
         L      R3,FRACS-8(R1)           n(j)
         MR     R4,R3                    *n(j)
         ST     R5,NN                    nn=nn/d(j)*n(j)
         B      LEAVEJ                   leave j
       ENDIF    ,                      end if
         LA     R7,1(R7)               j++
       ENDDO    ,                    end do j
LEAVEJ   LA     R6,1(R6)             i++
       ENDDO    ,                  end do i
         L      R13,4(0,R13)       restore previous savearea pointer
         RETURN (14,12),RC=0       restore registers from calling sav
NF       EQU    (TERMS-FRACS)/8    number of fracs
NN       DC     F'2'               nn
FRACS  DC  F'17',F'91',F'78',F'85',F'19',F'51',F'23',F'38',F'29',F'33'
       DC  F'77',F'29',F'95',F'23',F'77',F'19',F'1',F'17',F'11',F'13'
       DC  F'13',F'11',F'15',F'14',F'15',F'2',F'55',F'1'
TERMS    DC     F'100'             terms
PG       DC     CL80'*** :'        buffer
XDEC     DS     CL12               temp
         REGEQU
         END    FRACTRAN

Output:

  1 :           2
  2 :          15
  3 :         825
  4 :         725
  5 :        1925
  6 :        2275
  7 :         425
  8 :         390
  9 :         330
 10 :         290
...
 99 :        2128
100 :        1288

Ada

with Ada.Text_IO;

procedure Fractan is
   
   type Fraction is record Nom: Natural; Denom: Positive; end record;
   type Frac_Arr is array(Positive range <>) of Fraction;
   
   function "/" (N: Natural; D: Positive) return Fraction is
      Frac: Fraction := (Nom => N, Denom => D);
   begin
      return Frac;
   end "/";
   
   procedure F(List: Frac_Arr; Start: Positive; Max_Steps: Natural) is
      N: Positive := Start;
      J: Positive;
   begin
      Ada.Text_IO.Put(" 0:" & Integer'Image(N) & "   ");
      for I in 1 .. Max_Steps loop
	 J := List'First;
	 loop
	    if N mod List(J).Denom = 0 then
	       N := (N/List(J).Denom) * List(J).Nom;
	       exit; -- found fraction
	    elsif J >= List'Last then
	       return; -- did try out all fractions
	    else
	       J := J + 1; -- try the next fraction
	    end if;
	 end loop;
	 Ada.Text_IO.Put(Integer'Image(I) & ":" & Integer'Image(N) & "   ");
      end loop;
   end F;
   
begin
   -- F((2/3, 7/2, 1/5, 1/7, 1/9, 1/4, 1/8), 2, 100); 
   -- output would be "0: 2    1: 7    2: 1" and then terminate

   F((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), 
     2, 15);
   -- output is "0: 2    1: 15    2: 825    3: 725   ...   14: 132    15: 116"
end Fractan;

Output:

 0: 2    1: 15    2: 825    3: 725    4: 1925    5: 2275    6: 425    7: 390    8: 330    9: 290    10: 770    11: 910    12: 170    13: 156    14: 132    15: 116

ALGOL 68

Works with: ALGOL 68G version Any - tested with release 2.8.win32

# as the numbers required for finding the first 20 primes are quite large, #
# we use Algol 68G's LONG LONG INT with a precision of 100 digits          #
PR precision 100 PR

# mode to hold fractions #
MODE FRACTION = STRUCT( INT numerator, INT denominator );

# define / between two INTs to yield a FRACTION #
OP / = ( INT a, b )FRACTION: ( a, b );

# mode to define a FRACTRAN progam #
MODE FRACTRAN = STRUCT( FLEX[0]FRACTION data
                      , LONG LONG INT   n
                      , BOOL            halted
                      );
# prepares a FRACTRAN program for use - sets the initial value of n and halted to FALSE #
PRIO STARTAT = 1;
OP   STARTAT = ( REF FRACTRAN f, INT start )REF FRACTRAN:
BEGIN
    halted OF f := FALSE;
         n OF f := start;
    f
END;

# sets n OF f to the next number in the sequence or sets halted OF f to TRUE if the sequence has ended #
OP NEXT = ( REF FRACTRAN f )LONG LONG INT:
    IF halted OF f
    THEN n OF f := 0
    ELSE
        BOOL          found  := FALSE;
        LONG LONG INT result := 0;
        FOR pos FROM LWB data OF f TO UPB data OF f WHILE NOT found DO
            LONG LONG INT value       = n OF f * numerator OF ( ( data OF f )[ pos ] );
            INT           denominator = denominator OF ( ( data OF f )[ pos ] );
            IF found := ( value MOD denominator = 0 ) THEN result := value OVER denominator FI
        OD;
        IF NOT found THEN halted OF f := TRUE FI;
        n OF f := result
    FI ;

# generate and print the sequence of numbers from a FRACTRAN pogram #
PROC print fractran sequence = ( REF FRACTRAN f, INT start, INT limit )VOID:
BEGIN
    VOID( f STARTAT start );
    print( ( "0: ", whole( start, 0 ) ) );
    FOR i TO limit
    WHILE VOID( NEXT f );
          NOT halted OF f
    DO
        print( ( " " + whole( i, 0 ) + ": " + whole( n OF f, 0 ) ) )
    OD;
    print( ( newline ) )
END ;

# print the first 16 elements from the primes FRACTRAN program #
FRACTRAN pf := ( ( 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 ), 0, FALSE );
print fractran sequence( pf, 2, 15 );

# find some primes using the pf FRACTRAN progam - n is prime for the members in the sequence that are 2^n #
INT primes found := 0;
VOID( pf STARTAT 2 );
INT pos := 0;
print( ( "seq position  prime sequence value", newline ) );
WHILE primes found < 20 AND NOT halted OF pf DO
    LONG LONG INT value      := NEXT pf;
    INT      power of 2 := 0;
    pos +:= 1;
    WHILE value MOD 2 = 0 AND value > 0 DO power of 2 PLUSAB 1; value OVERAB 2 OD;
    IF value = 1 THEN
        # found a prime #
        primes found +:= 1;
        print( ( whole( pos, -12 ) + " " + whole( power of 2, -6 ) + " (" + whole( n OF pf, 0 ) + ")", newline ) )
    FI
OD

Output:

0: 2 1: 15 2: 825 3: 725 4: 1925 5: 2275 6: 425 7: 390 8: 330 9: 290 10: 770 11: 910 12: 170 13: 156 14: 132 15: 116
seq position  prime sequence value
          19      2 (4)
          69      3 (8)
         280      5 (32)
         707      7 (128)
        2363     11 (2048)
        3876     13 (8192)
        8068     17 (131072)
       11319     19 (524288)
       19201     23 (8388608)
       36866     29 (536870912)
       45551     31 (2147483648)
       75224     37 (137438953472)
      101112     41 (2199023255552)
      117831     43 (8796093022208)
      152025     47 (140737488355328)
      215384     53 (9007199254740992)
      293375     59 (576460752303423488)
      327020     61 (2305843009213693952)
      428553     67 (147573952589676412928)
      507519     71 (2361183241434822606848)

APL

Works with: Dyalog APL

fractran←{
    parts ← ' '∘≠⊆⊢
    frac ← ⍎¨'/'∘≠⊆⊢
    simp ← ⊢÷∨/
    mul ← simp×
    prog ← simp∘frac¨parts ⍺
    step ← {⊃⊃(1=2⊃¨next)/next←⍺ mul¨⊂(⍵ 1)}
    (start nstep)←⍵
    rslt ← ⊃(⊢,⍨prog∘step∘⊃)⍣nstep¨start
    ⌽(⊢(/⍨)(∨\0∘≠))rslt
}

Output:

      '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' fractran 2 20 
2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132 116 308 364 68 4 30

AutoHotkey

n := 2, steplimit := 15, numerator := [], denominator := []
s := "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"

Loop, Parse, s, % A_Space
    if (!RegExMatch(A_LoopField, "^(\d+)/(\d+)$", m))
        MsgBox, % "Invalid input string (" A_LoopField ")."
    else
        numerator[A_Index] := m1, denominator[A_Index] := m2

SetFormat, FloatFast, 0.0
Gui, Add, ListView, R10 W100 -Hdr, |
SysGet, VSBW, 2
LV_ModifyCol(1, 95 - VSBW), LV_Add( , 0 ": " n)
Gui, Show

Loop, % steplimit {
    i := A_Index
    Loop, % numerator.MaxIndex()
        if (!Mod(nn := n * numerator[A_Index] / denominator[A_Index], 1)) {
            LV_Modify(LV_Add( , i ": " (n := nn)), "Vis")
            continue, 2
        }
    break
}

Output:

bash

Works with: Bash

the "factor" command allows one to decrypt the data. For example, the program below computes the product of a and b, entered as 2^a and 3^b, the product being 5^a×b. Two arrays are computed from the fractions, ns for the numerators and ds for the denominators. Then, every time where the multiplication by a fraction yields an integer, the output of the division is stored into a csv file in factored format.

#! /bin/bash
program="1/1 455/33 11/13 1/11 3/7 11/2 1/3"
echo $program | tr " " "\n" | cut -d"/" -f1 | tr "\n" " " > "data"
read -a ns < "data"
echo $program | tr " " "\n" | cut -d"/" -f2 | tr "\n" " " > "data"
read -a ds < "data"


t=0
n=72
echo "steps of computation" > steps.csv
while [ $t -le 6 ]; do
	if [ $(($n*${ns[$t]}%${ds[$t]})) -eq 0 ]; then
		let "n=$(($n*${ns[$t]}/${ds[$t]}))"
		let "t=0"
		factor $n >> steps.csv
	fi
	let "t=$t+1"
done

If at the beginning n=72=2³×3² (to compute 3×2), the steps of the computation look like this:

steps of computation
72: 2 2 2 3 3
396: 2 2 3 3 11
5460: 2 2 3 5 7 13
4620: 2 2 3 5 7 11
63700: 2 2 5 5 7 7 13
53900: 2 2 5 5 7 7 11
4900: 2 2 5 5 7 7
2100: 2 2 3 5 5 7
900: 2 2 3 3 5 5
4950: 2 3 3 5 5 11
68250: 2 3 5 5 5 7 13
57750: 2 3 5 5 5 7 11
796250: 2 5 5 5 5 7 7 13
673750: 2 5 5 5 5 7 7 11
61250: 2 5 5 5 5 7 7
26250: 2 3 5 5 5 5 7
11250: 2 3 3 5 5 5 5
61875: 3 3 5 5 5 5 11
853125: 3 5 5 5 5 5 7 13
721875: 3 5 5 5 5 5 7 11
9953125: 5 5 5 5 5 5 7 7 13
8421875: 5 5 5 5 5 5 7 7 11
765625: 5 5 5 5 5 5 7 7
328125: 3 5 5 5 5 5 5 7
140625: 3 3 5 5 5 5 5 5
46875: 3 5 5 5 5 5 5
15625: 5 5 5 5 5 5

This file can be opened with a spreadsheet to draw the successive states of the prime numbers (with countif) and then look how the computation is done in successive steps.

Batch File

@echo off
setlocal enabledelayedexpansion

	::Set the inputs
set "code=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"
set "n=2"

	::Basic validation of code
for %%. in (!code!) do (
	echo.%%.|findstr /r /c:"^[0-9][0-9]*/[1-9][0-9]*$">nul||goto error_code
)
	::Validate the input
set /a "tst=1*!n!" 2>nul
if !tst! lss 0 goto error_input
if !tst! equ 0 (if not "!n!"=="0" (goto error_input))

	::Set the limit outputs
	set limit=20

	::Execute the code
echo.Input:
echo.	!n!
echo.Output:
for /l %%? in (1,1,!limit!) do (
	set shouldwehalt=1
	for %%A in (!code!) do (
		for /f "tokens=1,2 delims=/" %%B in ("%%A") do (
			set /a "tst=!n! %% %%C"
			if !tst! equ 0 (
				if !shouldwehalt! equ 1 (
					set shouldwehalt=0
					set /a "n=n*%%B/%%C"
					echo.	!n!
				)
			)
		)
	)
	if !shouldwehalt! equ 1 goto halt
)

:halt
echo.
pause
exit /b 0

:error_code
echo.Syntax error in code.
echo.
pause
exit /b 1

:error_input
echo.Invalid input.
echo.
pause
exit /b 1

Output:

Input:
        2
Output:
        15
        825
        725
        1925
        2275
        425
        390
        330
        290
        770
        910
        170
        156
        132
        116
        308
        364
        68
        4
        30

Press any key to continue . . .

Befunge

This takes as input a space-separated list of fractions, a starting value, and the number of iterations to output.

Note that in some interpreters you may need to press <Return> twice after entering the fractions if the Starting value prompt doesn't at first appear.

p0" :snoitcarF">:#,_>&00g5p~$&00g:v
v"Starting value: "_^#-*84~p6p00+1<
>:#,_&0" :snoitaretI">:#,_#@>>$&\:v
:$_\:10g5g*:10g6g%v1:\1$\$<|!:-1\.<
g0^<!:-1\p01+1g01$_10g6g/\^>\010p00

Output:

Fractions: 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 value: 2
Iterations: 16
2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132 116

BQN

The function RunFractran runs a fractran program, given max iterations on the left, and input, program string on the right. It returns a list of generated numbers.

Fractran performs a single iteration of fractran on a given input, list of numerators and list of denominators.

# Fractran interpreter

# Helpers
_while_ ← {𝔽⍟𝔾∘𝔽_𝕣_𝔾∘𝔽⍟𝔾𝕩}
ToInt ← 10⊸×⊸+˜´·⌽-⟜'0'
ToFrac ← {
  i ← ⊑/'/'=𝕩
  ToInt¨i(↑⋈1⊸+⊸↓)𝕩
}
Split ← ((¬-˜⊢×·+`»⊸>)∘≠⊔⊢)

Fractran ← {
  𝕊 n‿num‿den:
  ind ← ⊑/0=den|num×n
  ⟨(n×ind⊑num)÷ind⊑den ⋄ num ⋄ den⟩
}

RunFractran ← {
  steps 𝕊 inp‿prg:
  num‿den ← <˘⍉>ToFrac¨' 'Split prg
  step ← 1
  list ← ⟨inp⟩
  {
    step +↩ 1
    out ← Fractran 𝕩
    list ∾↩ ⊑out
    out
  } _while_ {𝕊 n‿num‿den: (step<steps)∧ ∨´0=den|num} inp‿num‿den
  list
}

seq ← 200 RunFractran 2‿"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"
•Out "Generated numbers: "∾•Repr seq
•Out "Primes: "∾•Repr 1↓⌊2⋆⁼(⌈=⌊)∘(2⊸(⋆⁼))⊸/ seq

   )ex fractran.bqn
Generated numbers: 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‿5320‿3220‿13300‿8050‿33250‿20125‿83125‿336875‿398125‿74375‿68250‿12750‿11700‿9900‿8700‿23100‿20300‿53900‿63700‿11900‿10920‿2040‿1872‿1584‿1392‿3696‿3248‿8624‿10192‿1904‿112‿120‿900‿6750‿50625‿2784375‿2446875‿6496875‿5709375‿15159375‿13321875‿35371875‿31084375‿82534375‿97540625‿18221875‿16721250‿3123750‿2866500‿535500‿491400‿91800‿84240‿71280‿62640‿166320‿146160‿388080‿341040‿905520‿795760‿2112880‿2497040‿466480‿428064‿79968‿29792‿18032‿74480‿45080‿186200‿112700‿465500‿281750‿1163750‿704375‿2909375‿11790625‿13934375‿2603125‿2388750‿446250‿409500‿76500‿70200‿59400‿52200‿138600‿121800‿323400‿284200‿754600‿891800‿166600‿152880‿28560‿26208‿4896‿1824‿1104
Primes: 2‿3

Bracmat

This program computes the first twenty primes. It has to do almost 430000 iterations to arrive at the twentieth prime, so instead of immediately writing each number to the terminal, it adds it to a list. After the set number of iterations, the list of numbers is written to a text file numbers.lst (21858548 bytes), so you can inspect it. Because it takes some time to do all iterations, its is advisable to write the source code below in a text file 'fractran' and run it in batch mode in the background, instead of starting Bracmat in interactive mode and typing the program at the prompt. The primes, together with the largest number found, are written to a file FRACTRAN.OUT.

(fractran=
  np n fs A Z fi P p N L M
.   !arg:(?N,?n,?fs)                 {Number of iterations, start n, fractions}
  & :?P:?L                           {Initialise accumulators.}
  &   whl
    ' ( -1+!N:>0:?N                  {Stop when counted down to zero.}
      & !n !L:?L                     {Prepend all numbers to result list.}
      & (2\L!n:#?p&!P !p:?P|)        {If log2(n) is rational, append it to list of primes.}
      & !fs:? (/?fi&!n*!fi:~/:?n) ?  {This line does the following (See task description):
                                      "for the first fraction, fi, in the list for which
                                       nfi is an integer, replace n by nfi ;"}
      )
  & :?M
  & whl'(!L:%?n ?L&!n !M:?M)         {Invert list of numbers. (append to long list is
                                      very expensive. Better to prepend and finally invert.}
  & (!M,!P)                          {Return the two lists}
);



( clk$:?t0
& fractran$(430000, 2, 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)
  : (?numbers,?primes)
& lst$(numbers,"numbers.lst",NEW)
& put$("
FRACTRAN found these primes:"
  !primes
  "\nThe list of numbers is saved in numbers.txt
The biggest number in the list is"
  (   0:?max
    & !numbers:? (>%@!max:?max&~) ?
  | !max
  )
str$("\ntime: " flt$(clk$+-1*!t0,4) " sec\n")
, "FRACTRAN.OUT",NEW)
);

In Linux, run the program as follows (assuming bracmat and the file 'fractran' are in the CWD):

./bracmat 'get$fractran' &

Output:

in FRACTRAN.OUT

FRACTRAN found these primes:
  1
  2
  3
  5
  7
  11
  13
  17
  19
  23
  29
  31
  37
  41
  43
  47
  53
  59
  61
  67

The list of numbers is saved in numbers.txt
The biggest number in the list is
  1842775069354845065175076326808495219647033145169559640049770986129640260031692378106527030467987060546875

time: 1,8668*10E3 sec

C

Using GMP. Powers of two are in brackets. For extra credit, pipe the output through | less -S.

#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>

typedef struct frac_s *frac;
struct frac_s {
	int n, d;
	frac next;
};

frac parse(char *s)
{
	int offset = 0;
	struct frac_s h = {0}, *p = &h;

	while (2 == sscanf(s, "%d/%d%n", &h.n, &h.d, &offset)) {
		s += offset;
		p = p->next = malloc(sizeof *p);
		*p = h;
		p->next = 0;
	}

	return h.next;
}

int run(int v, char *s)
{
	frac n, p = parse(s);
	mpz_t val;
	mpz_init_set_ui(val, v);

loop:	n = p;
	if (mpz_popcount(val) == 1)
		gmp_printf("\n[2^%d = %Zd]", mpz_scan1(val, 0), val);
	else
		gmp_printf(" %Zd", val);

	for (n = p; n; n = n->next) {
		// assuming the fractions are not reducible
		if (!mpz_divisible_ui_p(val, n->d)) continue;

		mpz_divexact_ui(val, val, n->d);
		mpz_mul_ui(val, val, n->n);
		goto loop;
	}

	gmp_printf("\nhalt: %Zd has no divisors\n", val);

	mpz_clear(val);
	while (p) {
		n = p->next;
		free(p);
		p = n;
	}

	return 0;
}

int main(void)
{
	run(2,	"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");

	return 0;
}

C#

The use of using Fractype = (BigInteger numerator, BigInteger denominator); requires C# 12.0.

namespace System.Numerics
{
    using Fractype = (BigInteger numerator, BigInteger denominator);
    struct Quotient
    {
        private Fractype _frac;
        public Fractype Fraction
        {
            get => _frac;
            set => _frac = Reduce(value);
        }

        public bool IsIntegral => _frac.denominator == 1;

        public Quotient(BigInteger num, BigInteger den)
        {
            Fraction = (num, den);
        }

        public static BigInteger GCD(BigInteger a, BigInteger b)
        {
            return (b == 0) ? a : GCD(b, a % b);
        }

        private static Fractype Reduce(Fractype f)
        {
            if (f.denominator == 0)
                throw new DivideByZeroException();

            BigInteger gcd = Quotient.GCD(f.numerator, f.denominator);
            return (f.numerator / gcd, f.denominator / gcd);
        }

        public static Quotient operator *(Quotient a, Quotient b)
            => new Quotient(a._frac.numerator * b._frac.numerator, a._frac.denominator * b._frac.denominator);

        public static Quotient operator *(Quotient a, BigInteger n)
            => new Quotient(a._frac.numerator * n, a._frac.denominator);

        public static explicit operator Quotient(Fractype t) => new Quotient(t.numerator, t.denominator);
    }

    class FRACTRAN
    {
        private Quotient[] code;
        public FRACTRAN(Fractype[] _code)
        {
            code = _code.Select(x => (Quotient) x).ToArray();
        }

        public (BigInteger value, bool success) Compute(BigInteger n)
        {
            for (int i = 0; i < code.Length; i++)
                if ((code[i] * n).IsIntegral)
                    return ((code[i] * n).Fraction.numerator, true);
            return (0, false);
        }
    }

    class Program
    {
        public static void Main(string[] args)
        { 
            Fractype[] frac_code = args[0].Split(" ")
                .Select(x => ((BigInteger)Int32.Parse(x.Split("/")[0]), (BigInteger)Int32.Parse(x.Split("/")[1].Trim(',')))).ToArray();
            BigInteger init = new BigInteger(Int32.Parse(args[1].Trim(',')));
            int steps = Int32.Parse(args[2].Trim(','));
            
            FRACTRAN FRACGAME = new FRACTRAN(frac_code);

            List<BigInteger> sequence = new List<BigInteger>();
            sequence.Add(init);
            bool halt = false;
            for (int i = 0; i < steps - 1; i++)
            {
                var k = FRACGAME.Compute(sequence[sequence.Count - 1]);
                if (k.success)
                    sequence.Add(k.value);
                else
                {
                    halt = true;
                    break;
                }
            }

            for (int i = 0; i < sequence.Count; i++)
                Console.WriteLine((i + 1).ToString() + ": " + sequence[i]);
            if (halt)
                Console.WriteLine("HALT");
        }
    }
}

Input:

"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", 2, 15

Output:

Moreover, modifying the class Program to,

    class Program
    {
        private static bool PowerOfTwo(BigInteger b)
        {
            while (b % 2 == 0)
                b /= 2;
            return b == 1;
        }

        private static BigInteger BigLog2(BigInteger b)
        {
            BigInteger r = 0;
            while (b > 1)
            {
                r++;
                b /= 2;
            }
            return r;
        }
        
        public static void Main(string[] args)
        { 
            Fractype[] frac_code = args[0].Split(" ")
                .Select(x => ((BigInteger)Int32.Parse(x.Split("/")[0]), (BigInteger)Int32.Parse(x.Split("/")[1].Trim(',')))).ToArray();
            BigInteger init = new BigInteger(Int32.Parse(args[1].Trim(',')));
            int steps = Int32.Parse(args[2].Trim(','));
            
            FRACTRAN FRACGAME = new FRACTRAN(frac_code);

            List<BigInteger> sequence = new List<BigInteger>();
            List<BigInteger> primes = new List<BigInteger>();
            sequence.Add(init);
            bool halt = false;
            while (primes.Count() < 20)
            {
                var k = FRACGAME.Compute(sequence[sequence.Count - 1]);
                if (k.success)
                    sequence.Add(k.value);
                else
                {
                    halt = true;
                    break;
                }
                
                if (PowerOfTwo(k.value))
                    primes.Add(BigLog2(k.value));
            }

            for (int i = 0; i < primes.Count; i++)
                Console.WriteLine((i + 1).ToString() + ": " + primes[i]);
            if (halt)
                Console.WriteLine("HALT");
        }
    }

with the same input, will print the first 20 primes.

C++

#include <iostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <cmath>

using namespace std;

class fractran
{
public:
    void run( std::string p, int s, int l  )
    {
        start = s; limit = l;
        istringstream iss( p ); vector<string> tmp;
        copy( istream_iterator<string>( iss ), istream_iterator<string>(), back_inserter<vector<string> >( tmp ) );

        string item; vector< pair<float, float> > v;
	pair<float, float> a;
	for( vector<string>::iterator i = tmp.begin(); i != tmp.end(); i++ )
	{
	    string::size_type pos = ( *i ).find( '/', 0 );
	    if( pos != std::string::npos )
	    {
		a = make_pair( atof( ( ( *i ).substr( 0, pos ) ).c_str() ), atof( ( ( *i ).substr( pos + 1 ) ).c_str() ) );
		v.push_back( a );
	    }
	}
		
	exec( &v );
    }

private:
    void exec( vector< pair<float, float> >* v )
    {
	int cnt = 0;
	while( cnt < limit )
	{
	    cout << cnt << " : " << start << "\n";
	    cnt++;
	    vector< pair<float, float> >::iterator it = v->begin();
	    bool found = false; float r;
	    while( it != v->end() )
	    {
		r  = start * ( ( *it ).first / ( *it ).second );
		if( r == floor( r ) )
		{
		    found = true;
		    break;
		}
		++it;
	    }

	    if( found ) start = ( int )r;
	    else break;
	}
    }
    int start, limit;
};
int main( int argc, char* argv[] )
{
    fractran f; f.run( "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", 2, 15 );
    cin.get();
    return 0;
}

Output:

CLU

ratio = cluster is new, parse, unparse, get_num, get_denom, mul
    rep = struct[num, denom: int]
    
    new = proc (num, denom: int) returns (cvt)
        return(simplify(rep${num: num, denom: denom}))
    end new
    
    parse = proc (rat: string) returns (ratio) signals (bad_format)
        rat := trim(rat)
        sep: int := string$indexc('/', rat)
        if sep = 0 then signal bad_format end
        
        num: string := string$substr(rat, 1, sep-1)
        denom: string := string$rest(rat, sep+1)
        return(new(int$parse(num), int$parse(denom))) resignal bad_format
    end parse
    
    trim = proc (s: string) returns (string)
        start: int := 1
        while start <= string$size(s) cand s[start] = ' ' do start := start + 1 end 
        
        end_: int := string$size(s)
        while end_ >= 1 cand s[end_] = ' ' do end_ := end_ - 1 end
        return(string$substr(s, start, end_-start+1))
    end trim
    
    unparse = proc (rat: cvt) returns (string)
        return(int$unparse(rat.num) || "/" || int$unparse(rat.denom))
    end unparse
    
    get_num = proc (rat: cvt) returns (int)
        return(rat.num)
    end get_num
    
    get_denom = proc (rat: cvt) returns (int)
        return(rat.denom)
    end get_denom
    
    mul = proc (a, b: cvt) returns (ratio)
        return(new(a.num * b.num, a.denom * b.denom))
    end mul 
    
    simplify = proc (rat: rep) returns (rep)
        num: int := int$abs(rat.num)
        denom: int := int$abs(rat.denom)
        
        sign: int
        if (rat.num < 0) = (rat.denom < 0)
            then sign := 1
            else sign := -1
        end
        
        factor: int := gcd(num, denom)
        return(rep${num: sign*num/factor, denom: denom/factor})
    end simplify
        
    gcd = proc (a, b: int) returns (int)
        while b ~= 0 do
            a, b := b, a // b
        end
        return(a)
    end gcd
end ratio

fractran = cluster is parse, run
    rep = sequence[ratio]
    
    parse = proc (program: string) returns (cvt)
        parsed: array[ratio] := array[ratio]$[]
        for rat: ratio in ratioes(program) do
            array[ratio]$addh(parsed, rat)
        end
        return(rep$a2s(parsed))
    end parse

    ratioes = iter (program: string) yields (ratio)
        while true do
            sep: int := string$indexc(',', program)
            if sep = 0 then
                yield(ratio$parse(program))
                break
            else
                yield(ratio$parse(string$substr(program, 1, sep-1)))
                program := string$rest(program, sep+1)
            end
        end
    end ratioes
    
    run = iter (program: cvt, n, maxiter: int) yields (int)
        nrat: ratio := ratio$new(n, 1)
        while maxiter > 0 do
            yield(nrat.num)
            begin
                for rat: ratio in rep$elements(program) do
                    mul: ratio := rat * nrat
                    if mul.denom = 1 then
                        exit found(mul)
                    end
                end
                break
            end except when found(new: ratio):
                nrat := new
            end
            maxiter := maxiter - 1
        end
    end run
end fractran

start_up = proc ()
    po: stream := stream$primary_output()
    
    program: string := "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"
    parsed: fractran := fractran$parse(program)
    
    index: int := 0
    for result: int in fractran$run(parsed, 2, 20) do
        stream$putright(po, int$unparse(index), 3)
        stream$putc(po, ':')
        stream$putright(po, int$unparse(result), 10)
        stream$putl(po, "")
        index := index + 1
    end
end start_up

Output:

  0:         2
  1:        15
  2:       825
  3:       725
  4:      1925
  5:      2275
  6:       425
  7:       390
  8:       330
  9:       290
 10:       770
 11:       910
 12:       170
 13:       156
 14:       132
 15:       116
 16:       308
 17:       364
 18:        68
 19:         4

Common Lisp

(defun fractran (n frac-list)
  (lambda ()
    (prog1
      n
      (when n
        (let ((f (find-if (lambda (frac)
                            (integerp (* n frac)))
                          frac-list)))
          (when f (setf n (* f n))))))))


;; test

(defvar *primes-ft* '(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))

(loop with fractran-instance = (fractran 2 *primes-ft*)
      repeat 20
      for next = (funcall fractran-instance)
      until (null next)
      do (print next))

Output:

D

Simple Version

Translation of: Java

import std.stdio, std.algorithm, std.conv, std.array;

void fractran(in string prog, int val, in uint limit) {
    const fracts = prog.split.map!(p => p.split("/").to!(int[])).array;

    foreach (immutable n; 0 .. limit) {
        writeln(n, ": ", val);
        const found = fracts.find!(p => val % p[1] == 0);
        if (found.empty)
            break;
        val = found.front[0] * val / found.front[1];
    }
}

void main() {
    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", 2, 15);
}

Output:

Lazy Version

import std.stdio, std.algorithm, std.conv, std.array, std.range;

struct Fractran {
    int front;
    bool empty = false;
    const int[][] fracts;

    this(in string prog, in int val) {
        this.front = val;
        fracts = prog.split.map!(p => p.split("/").to!(int[])).array;
    }

    void popFront() {
        const found = fracts.find!(p => front % p[1] == 0);
        if (found.empty)
            empty = true;
        else
            front = found.front[0] * front / found.front[1];
    }
}

void main() {
    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", 2)
    .take(15).writeln;
}

Output:

[2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132]

Delphi

Library: System.SysUtils

Library: System.RegularExpressions

Translation of: Java

program FractranTest;

{$APPTYPE CONSOLE}

uses
  System.SysUtils,
  System.RegularExpressions;

type
  TFractan = class
  private
    limit: Integer;
    num, den: TArray<Integer>;
    procedure compile(prog: string);
    procedure exec(val: Integer);
    function step(val: Integer): integer;
    procedure dump();
  public
    constructor Create(prog: string; val: Integer);
  end;

{ TFractan }

constructor TFractan.Create(prog: string; val: Integer);
begin
  limit := 15;
  compile(prog);
  dump();
  exec(2);
end;

procedure TFractan.compile(prog: string);
var
  reg: TRegEx;
  m: TMatch;
begin
  reg := TRegEx.Create('\s*(\d*)\s*\/\s*(\d*)\s*');
  m := reg.Match(prog);
  while m.Success do
  begin
    SetLength(num, Length(num) + 1);
    num[high(num)] := StrToIntDef(m.Groups[1].Value, 0);

    SetLength(den, Length(den) + 1);
    den[high(den)] := StrToIntDef(m.Groups[2].Value, 0);

    m := m.NextMatch;
  end;
end;

procedure TFractan.exec(val: Integer);
var
  n: Integer;
begin
  n := 0;
  while (n < limit) and (val <> -1) do
  begin
    Writeln(n, ': ', val);
    val := step(val);
    inc(n);
  end;
end;

function TFractan.step(val: Integer): integer;
var
  i: integer;
begin
  i := 0;
  while (i < length(den)) and (val mod den[i] <> 0) do
    inc(i);
  if i < length(den) then
    exit(round(num[i] * val / den[i]));
  result := -1;
end;

procedure TFractan.dump();
var
  i: Integer;
begin
  for i := 0 to high(den) do
    Write(num[i], '/', den[i], ' ');
  Writeln;
end;

const
  DATA =
    '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';

begin
  TFractan.Create(DATA, 2).Free;
  Readln;
end.

Output:

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
0: 2
1: 15
2: 825
3: 725
4: 1925
5: 2275
6: 425
7: 390
8: 330
9: 290
10: 770
11: 910
12: 170
13: 156
14: 132

Elixir

Translation of: Erlang

defmodule Fractran do
  use Bitwise
  
  defp binary_to_ratio(b) do
    [_, num, den] = Regex.run(~r/(\d+)\/(\d+)/, b)
    {String.to_integer(num), String.to_integer(den)}
  end
  
  def load(program) do
    String.split(program) |> Enum.map(&binary_to_ratio(&1))
  end
  
  defp step(_, []), do: :halt
  defp step(n, [f|fs]) do
    {p, q} = mulrat(f, {n, 1})
    case q do
        1 -> p
        _ -> step(n, fs)
    end
  end
  
  def exec(k, n, program) do
    exec(k-1, n, fn (_) -> true end, program, [n]) |> Enum.reverse
  end
  
  def exec(k, n, pred, program) do
    exec(k-1, n, pred, program, [n]) |> Enum.reverse
  end
  
  defp exec(0, _, _, _, steps), do: steps
  defp exec(k, n, pred, program, steps) do
    case step(n, program) do
        :halt -> steps
        m -> if pred.(m), do: exec(k-1, m, pred, program, [m|steps]),
                        else: exec(k, m, pred, program, steps)
    end
  end
  
  def is_pow2(n), do: band(n, n-1) == 0
  
  def lowbit(n), do: lowbit(n, 0)
  
  defp lowbit(n, k) do
    case band(n, 1) do
        0 -> lowbit(bsr(n, 1), k + 1)
        1 -> k
    end
  end
  
  # rational multiplication
  defp mulrat({a, b}, {c, d}) do
    {p, q} = {a*c, b*d}
    g = gcd(p, q)
    {div(p, g), div(q, g)}
  end
  
  defp gcd(a, 0), do: a
  defp gcd(a, b), do: gcd(b, rem(a, b))
end

primegen = Fractran.load("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")
IO.puts "The first few states of the Fractran prime automaton are:\n#{inspect Fractran.exec(20, 2, primegen)}\n"
prime = Fractran.exec(26, 2, &Fractran.is_pow2/1, primegen)
        |> Enum.map(&Fractran.lowbit/1)
        |> tl
IO.puts "The first few primes are:\n#{inspect prime}"

Output:

The first few states of the Fractran prime automaton are:
[2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4]

The first few primes are:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Erlang

The exec() function can be passed a predicate which filters steps that satisfy a condition, which for the prime automata is a check to see if the number is a power of 2.

#! /usr/bin/escript

-mode(native).
-import(lists, [map/2, reverse/1]).

binary_to_ratio(B) ->
    {match, [_, Num, Den]} = re:run(B, "([0-9]+)/([0-9]+)"),
    {binary_to_integer(binary:part(B, Num)),
     binary_to_integer(binary:part(B, Den))}.

load(Program) ->
    map(fun binary_to_ratio/1, re:split(Program, "[ ]+")).

step(_, []) -> halt;
step(N, [F|Fs]) ->
    {P, Q} = mulrat(F, {N, 1}),
    case Q of
        1 -> P;
        _ -> step(N, Fs)
    end.

exec(K, N, Program) -> reverse(exec(K - 1, N, fun (_) -> true end, Program, [N])).
exec(K, N, Pred, Program) -> reverse(exec(K - 1, N, Pred, Program, [N])).

exec(0, _, _, _, Steps) -> Steps;
exec(K, N, Pred, Program, Steps) ->
    case step(N, Program) of
        halt -> Steps;
        M -> case Pred(M) of 
                true  -> exec(K - 1, M, Pred, Program, [M|Steps]);
                false -> exec(K, M, Pred, Program, Steps)
            end
    end.


is_pow2(N) -> N band (N - 1) =:= 0.

lowbit(N) -> lowbit(N, 0).
lowbit(N, K) ->
    case N band 1 of
        0 -> lowbit(N bsr 1, K + 1);
        1 -> K
    end.

main(_) ->
    PrimeGen = load("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"),
    io:format("The first few states of the Fractran prime automaton are: ~p~n~n", [exec(20, 2, PrimeGen)]),
    io:format("The first few primes are: ~p~n", [tl(map(fun lowbit/1, exec(26, 2, fun is_pow2/1, PrimeGen)))]).


% rational multiplication

mulrat({A, B}, {C, D}) ->
    {P, Q} = {A*C, B*D},
    G = gcd(P, Q),
    {P div G, Q div G}.

gcd(A, 0) -> A;
gcd(A, B) -> gcd(B, A rem B).

Output:

└─ $ ▶ ./fractran.erl 
The first few states of the Fractran prime automaton are: [2,15,825,725,1925,
                                                           2275,425,390,330,
                                                           290,770,910,170,
                                                           156,132,116,308,
                                                           364,68,4]

The first few primes are: [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,
                           67,71,73,79,83,89,97]

Factor

USING: io kernel math math.functions math.parser multiline
prettyprint sequences splitting ;
IN: rosetta-code.fractran

STRING: fractran-string
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
;

: fractran-parse ( str -- seq )
    " \n" split [ string>number ] map ;
    
: fractran-step ( seq n -- seq n'/f )
    2dup [ * integer? ] curry find nip dup [ * ] [ nip ] if ;
    
: fractran-run-full ( seq n -- )
    [ dup ] [ dup . fractran-step ] while 2drop ;
    
: fractran-run-limited ( seq n steps -- )
    [ dup pprint bl fractran-step ] times 2drop nl ;
    
: fractran-primes ( #primes seq n -- )
    [ pick zero? ] [
        dup 2 logn dup [ floor 1e-9 ~ ] [ 1. = not ] bi and [
            dup 2 logn >integer pprint bl [ 1 - ] 2dip
        ] when fractran-step
    ] until 3drop nl ;
    
: main ( -- )
    fractran-string fractran-parse 2
    [ "First 20 numbers: " print 20 fractran-run-limited nl ]
    [ "First 20 primes: " print [ 20 ] 2dip fractran-primes ]
    2bi ;
    
MAIN: main

Output:

First 20 numbers: 
2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132 116 308 364 68 4 

First 20 primes: 
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71

Fermat

Func FT( arr, n, m ) =
    ;{executes John H. Conway's FRACTRAN language for a program stored in [arr], an}
    ;{input integer stored in n, for a maximum of m steps}
    ;{To allow the program to run indefinitely, give it negative or noninteger m}
    exec:=1;                 {boolean to track whether the program needs to halt}
    len:=Cols[arr];          {length of the input program}
    while exec=1 and m<>0 do
        m:-;                 
        !!n;                 {output the memory}
        i:=1;                {index variable}
        exec:=0;
        while i<=len and exec=0 do
            nf:=n*arr[i];
            if Denom(nf) = 1 then
                n:=nf;       {did we find an instruction to execute?}
                exec:=1
            fi;
            i:+;
        od;
    od;
.;

;{Here is the program to run}
[arr]:=[( 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 )];

FT( [arr], 2, 20 );

Output:

2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132 116 308 364 68 4

Fortran

The Plan

As ever, how long is a piece of string: what might be the upper limit for the list of fractions? Similarly, obtaining the source code to be interpreted is a nuisance since as ever, one doesn't know how long it might be and performing a scan to find out will require more messing about than the activity of interest. One could compile in the specified example, but this is not very flexible even though a re-compilation will be swift. So, a pre-emptive requirement: first specify the number of fractions to be read in. Then reading the fractions has its annoyances also (aside from copying from the example text carrying along all the .html formatting) since given 2/3 a slash is not a suitable delimiter for free-format input, indeed it signifies end-of-input. Again, one can devise an input procedure involving a suitable scan, with more code drowning the stuff specific to the task. So, replace the slashes with a space, an acceptable free-format delimiter. As a comma is also acceptable, use those between the fractions, so, 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 Then, all that remains is to specify the starting number, and as well, a step limit. Naturally, the output can be in a more gracious form. It is presented as the input is read so that should something go awry there would be some indication of what was going on.

The Code

The source style is F77 except for the use of the I0 format code, though not all F77 compilers will offer INTEGER*8. By not using the MODULE scheme, array parameters can't be declared via P(:) which implies a secret additional parameter giving the size of the array and which can be accessed via the likes of UBOUND(P, DIM = 1) Instead, the old-style specification involves no additional parameters and can be given as P(*) meaning "no statement" as to the upper bound, or P(M) which may be interpreted as the upper bound being the value of M in the compilers that allow this. The actual upper bound of the parameter is unknown and unchecked, so the older style of P(12345) or similar might be used. Rather to my surprise, this compiler (Compaq F90/95) complained if parameter M was declared after the arrays P(M),Q(M) as it is my habit to declare parameters in the order of their appearance.

C:\Nicky\RosettaCode\FRACTRAN\FRACTRAN.for(6) : Warning: This name has not been given an explicit type.   [M]
       INTEGER P(M),Q(M)!The terms of the fractions.

So much for multi-pass compilers!

Similarly, without the MODULE protocol, in all calling routines function FRACTRAN would be deemed floating-point so a type declaration is needed in each.

      INTEGER FUNCTION FRACTRAN(N,P,Q,M)	!Notion devised by J. H. Conway.
Careful: the rule is N*P/Q being integer. N*6/3 is integer always because this is N*2/1, but 3 may not divide N.
Could check GCD(P,Q), dividing out the common denominator so MOD(N,Q) works.
       INTEGER*8 N	!The work variable. Modified!
       INTEGER M	!The number of fractions supplied.
       INTEGER P(M),Q(M)!The terms of the fractions.
       INTEGER I	!A stepper.
        DO I = 1,M	!Search the supplied fractions, P(i)/Q(i).
          IF (MOD(N,Q(I)).EQ.0) THEN	!Does the denominator divide N?
            N = N/Q(I)*P(I)	!Yes, compute N*P/Q but trying to dodge overflow.
            FRACTRAN = I	!Report the hit.
           RETURN		!Done!
          END IF	!Otherwise,
        END DO		!Try the next fraction in the order supplied.
        FRACTRAN = 0	!No hit.
      END FUNCTION FRACTRAN	!That's it! Even so, "Turing complete"...

      PROGRAM POKE
      INTEGER FRACTRAN		!Not the default type of function.
      INTEGER P(66),Q(66)	!Holds the fractions as P(i)/Q(i).
      INTEGER*8 N		!The working number.
      INTEGER I,IT,L,M		!Assistants.

      WRITE (6,1)	!Announce.
    1 FORMAT ("Interpreter for J.H. Conway's FRACTRAN language.")

Chew into an example programme.
      OPEN (10,FILE = "Fractran.txt",STATUS="OLD",ACTION="READ")	!Rather than compiled-in stuff.
      READ (10,*) L	!I need to know this without having to scan the input.
      WRITE (6,2) L	!Reveal in case of trouble.
    2 FORMAT (I0," fractions, as follow:")	!Should the input evoke problems.
      READ (10,*) (P(I),Q(I),I = 1,L)	!Ask for the specified number of P,Q pairs.
      WRITE (6,3) (P(I),Q(I),I = 1,L)	!Show what turned up.
    3 FORMAT (24(I0,"/",I0:", "))	!As P(i)/Q(i) pairs. The colon means that there will be no trailing comma.
      READ (10,*) N,M			!The start value, and the step limit.
      CLOSE (10)			!Finished with input.
      WRITE (6,4) N,M			!Hopefully, all went well.
    4 FORMAT ("Start with N = ",I0,", step limit ",I0)

Commence.
      WRITE (6,10) 0,N		!Splat a heading.
   10 FORMAT (/,"  Step  #F: N",/,I6,4X,": ",I0)	!Matched FORMAT 11.
      DO I = 1,M		!Here we go!
        IT = FRACTRAN(N,P,Q,L)		!Do it!
        WRITE (6,11) I,IT,N		!Show it!
   11   FORMAT (I6,I4,": ",I0)		!N last, as it may be big.
        IF (IT.LE.0) EXIT		!No hit, so quit.
      END DO			!The next step.
      END	!Whee!

The Results

Output:

Interpreter for J.H. Conway's FRACTRAN language.
14 fractions, as follow:
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
Start with N = 2, step limit 28

  Step  #F: N
     0    : 2
     1  13: 15
     2  14: 825
     3   5: 725
     4   6: 1925
     5  11: 2275
     6   1: 425
     7   2: 390
     8  10: 330
     9   5: 290
    10   6: 770
    11  11: 910
    12   1: 170
    13   2: 156
    14  10: 132
    15   5: 116
    16   6: 308
    17  11: 364
    18   1: 68
    19   9: 4
    20  13: 30
    21  13: 225
    22  14: 12375
    23   5: 10875
    24   6: 28875
    25   5: 25375
    26   6: 67375
    27  11: 79625
    28   1: 14875

Later Fortrans might offer the library function POPCNT(n) which returns the number of on-bits in an integer, most convenient for detecting a straight power of two in a binary computer. Adjusting the interpretation loop to be

      DO I = 1,M		!Here we go!
        IT = FRACTRAN(N,P,Q,L)		!Do it!
        IF (POPCNT(N).EQ.1) WRITE (6,11) I,IT,N		!Show it!
   11   FORMAT (I6,I4,": ",I0)		!N last, as it may be big.
        IF (IT.LE.0) EXIT		!No hit, so quit.
        IF (N.LE.0) THEN		!Otherwise, worry about overflow.
          WRITE (6,*) "Integer overflow!"	!Justified. The test is not certain.
          WRITE (6,11) I,IT,N			!Alas, the step failed.
          EXIT					!Give in.
        END IF				!So much for overflow.
      END DO			!The next step.

Leads to the following output:

Interpreter for J.H. Conway's FRACTRAN language.
14 fractions, as follow:
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
Start with N = 2, step limit 246810

  Step  #F: N
     0    : 2
    19   9: 4
    69   9: 8
   280   9: 32
   707   9: 128
  2363   9: 2048
 Integer overflow!
  2863   6: -3816591145242754741

And no, fraction #9 is not always the one with the power of two only, for instance step 130 with N = 2⁴x7. So, even a 64-bit integer is not enough, and with a 32-bit integer,

 Integer overflow!
   296   6: -1406264171

In the absence of a proper test such as the IF OVERFLOW ... of First Fortran (1957), the check for overflow relies on the improper appearance of negative numbers during two's-complement binary arithmetic that should only produce positive numbers. This will catch about half the events: N*M might or might not leave the sign bit on when the result overflows.

Revised Plan

One could introduce a scheme for multi-precision (or "bignum") arithmetic, but there is no need to maintain a unified number N because there are no additions or subtractions, only multiplications and division without remainders. In other words, why not mess about with collections of prime factors? That is, represent N, P, and Q as the list of prime numbers with their powers for each case. To calculate N*P, just add the list of prime number powers for P to that for N, and similarly, for N/Q subtract. At no stage (except perhaps to decorate output or for debugging) need the list be multiplied out to give the unified number and so there is no need for multi-precision multiplies and divides. To determine if N is divisible by Q (that is, if N*fraction = N*P/Q is integral), check only that the primes listed by Q have powers no greater than those of the corresponding primes for N.

To facilitate access without searching the list of primes for N, instead its list is represented by an array of powers, NPPOW, with most entries zero. Thus, NPPOW(i) has the power for PRIME(i) in the factorisation of N, and for N = 2, NPPOW(1) = 1 with all other elements zero. But for FP (the factorisation of P) and FQ (for Q) there is a proper list provided via type FACTORED, whereby FP.PLIST(0) is the count of prime factors and FP.PLIST(1:FP.PLIST(0)) fingers the prime numbers that are factors, with FP.PPOW(i) having their corresponding powers. Thus, FP.PLIST(2) has the index of the second prime factor of P (should it have so many), which is PRIME(FP.PLIST(2)), and its power is FP.PPOW(2). Accordingly, to determine if N (as NPPOW) is divisible by one of the fractions FQ, the appropriate elements of NPPOW (that give its powers) must be compared to the corresponding powers in FQ.PPOW, and if ALL of the powers in NPPOW fingered by FQ.PLIST are greater than or equal to those in FQ.PPOW, then a hit! For this purpose, the factorisation of a prime number includes that prime number. Note that the prime number factorisation of one has no elements in its list, and happily, the ALL operation applied for no tests yields true as desired, because one divides any number. Thus, in the FRACTRAN op-code system, a fraction P/1 is always a match, and no fractions beyond it will ever be considered.

As a part of the preparation, for each fraction the greatest common divisor is divided out to remove the possibility that converting the test N times fraction being integral via fraction = P/Q to Q divides N will behave differently. For example, N*6/3 will always be integral, but N may not be divisible by three. Reducing 6/3 to 2/1 however will work as will reducing 55/25 to 11/5. The example contains no such occasions, but the possibility nags.

For output, the value of N will not be shown multiplied out but via a schedule showing the powers of the first few prime numbers that form its factorisation. Rather than staring in puzzlement at opaque monster strings of digits, one can view each separate prime factor's power counting up and down as the calculation proceeds. A simple scan of all the factorisations soon determines the highest prime employed, and this never changes. An extension of this checks for which primes are omitted, and in this example, none are. However, a further extension modifies the output of the schedule of powers so as to blank out those that are zero. This could be achieved by replacing the likes of WRITE (...) NPPOW by WRITE (...) I6FMT(NPPOW) where function I6FMT writes out its integer with I6 format if the value is positive, and supplies six spaces if not, were it not that few Fortran systems allow such re-entrant usage of the system for formatted output. So, prepare the output with a straightforward WRITE to a CHARACTER variable, blank out the portions where unwanted values appear, and write the result.

Revised Code

Because this scheme requires a supply of prime numbers, it is convenient to employ the routines prepared for the extensible prime generator via module PRIMEBAG. So, this means escalating to the F90 style, and given that, some compound data structures can be used (for better mnemonics) in place of collections of arrays.

       MODULE CONWAYSIDEA	!Notion devised by J. H. Conway.
       USE PRIMEBAG		!This is a common need.
       INTEGER LASTP,ENUFF	!Some size allowances.
       PARAMETER (LASTP = 66, ENUFF = 66)	!Should suffice for the example in mind.
       INTEGER NPPOW(1:LASTP)	!Represent N as a collection of powers of prime numbers.
       TYPE FACTORED		!But represent P and Q of freaction = P/Q
        INTEGER PNUM(0:LASTP)	!As a list of prime number indices with PNUM(0) the count.
        INTEGER PPOW(LASTP)	!And the powers. for the fingered primes.
       END TYPE FACTORED	!Rather than as a simple number multiplied out.
       TYPE(FACTORED) FP(ENUFF),FQ(ENUFF)	!Thus represent a factored fraction, P(i)/Q(i).
       INTEGER PLIVE(ENUFF),NL	!Helps subroutine SHOWN display NPPOW.
       CONTAINS		!Now for the details.
        SUBROUTINE SHOWFACTORS(N)	!First, to show an internal data structure.
         TYPE(FACTORED) N	!It is supplied as a list of prime factors.
         INTEGER I		!A stepper.
          DO I = 1,N.PNUM(0)	!Step along the list.
            IF (I.GT.1) WRITE (MSG,"('x',$)")	!Append a glyph for "multiply".
            WRITE (MSG,"(I0,$)") PRIME(N.PNUM(I))	!The prime fingered in the list.
            IF (N.PPOW(I).GT.1) WRITE (MSG,"('^',I0,$)") N.PPOW(I)	!With an interesting power?
          END DO		!On to the next element in the list.
          WRITE (MSG,1) N.PNUM(0)	!End the line
    1     FORMAT (": Factor count ",I0)	!With a count of prime factors.
        END SUBROUTINE SHOWFACTORS	!Hopefully, this will not be needed often.

        TYPE(FACTORED) FUNCTION FACTOR(IT)	!Into a list of primes and their powers.
         INTEGER IT,N	!The number and a copy to damage.
         INTEGER P,POW	!A stepper and a power.
         INTEGER F,NF	!A factor and a counter.
          IF (IT.LE.0) STOP "Factor only positive numbers!"	!Or else...
          N = IT	!A copy I can damage.
          NF = 0	!No factors found.
          P = 0		!Because no primes have been tried.
       PP:DO WHILE (N.GT.1)	!Step through the possibilities.
       	    P = P + 1		!Another prime impends.
            F = PRIME(P)	!Grab a possible factor.
            POW = 0		!It has no power yet.
         FP:DO WHILE(MOD(N,F).EQ.0)	!Well?
              POW = POW + 1			!Count a factor..
              N = N/F				!Reduce the number.
            END DO FP			!The P'th prime's power's produced.
            IF (POW.GT.0) THEN	!So, was it a factor?
              IF (NF.GE.LASTP) THEN	!Yes. Have I room in the list?
                WRITE (MSG,1) IT,LASTP	!Alas.
    1           FORMAT ("Factoring ",I0," but with provision for only ",
     1           I0," prime factors!")
                FACTOR.PNUM(0) = NF	!Place the count so far,
                CALL SHOWFACTORS(FACTOR)!So this can be invoked.
                STOP "Not enough storage!"	!Quite.
              END IF			!But normally,
              NF = NF + 1		!Admit another factor.
              FACTOR.PNUM(NF) = P	!Identify the prime. NOT the prime itself.
              FACTOR.PPOW(NF) = POW	!Place its power.
            END IF		!So much for that factor.
          END DO PP	!Try another prime, if N > 1 still.
          FACTOR.PNUM(0) = NF	!Place the count.
        END FUNCTION FACTOR	!Thus, a list of primes and their powers.

        INTEGER FUNCTION GCD(I,J)	!Greatest common divisor.
         INTEGER I,J	!Of these two integers.
         INTEGER N,M,R	!Workers.
          N = MAX(I,J)	!Since I don't want to damage I or J,
          M = MIN(I,J)	!These copies might as well be the right way around.
    1     R = MOD(N,M)		!Divide N by M to get the remainder R.
          IF (R.GT.0) THEN	!Remainder zero?
            N = M			!No. Descend a level.
            M = R			!M-multiplicity has been removed from N.
            IF (R .GT. 1) GO TO 1	!No point dividing by one.
          END IF			!If R = 0, M divides N.
          GCD = M			!There we are.
        END FUNCTION GCD	!Euclid lives on!

        INTEGER FUNCTION FRACTRAN(L)	!Applies Conway's idea to a list of fractions.
Could abandon all parameters since global variables have the details...
         INTEGER L	!The last fraction to consider.
         INTEGER I,NF	!Assistants.
          DO I = 1,L		!Step through the fractions in the order they were given.
            NF = FQ(I).PNUM(0)	!How many factors are listed in FQ(I)?
            IF (ALL(NPPOW(FQ(I).PNUM(1:NF))	!Can N (as NPPOW) be divided by Q (as FQ)?
     1       .GE.         FQ(I).PPOW(1:NF))) THEN	!By comparing the supplies of prime factors.
              FRACTRAN = I			!Yes!
              NPPOW(FQ(I).PNUM(1:NF)) = NPPOW(FQ(I).PNUM(1:NF))	!Remove prime powers from N
     1            - FQ(I).PPOW(1:NF)				!Corresponding to Q.
              NF = FP(I).PNUM(0)				!Add powers to N
              NPPOW(FP(I).PNUM(1:NF)) = NPPOW(FP(I).PNUM(1:NF))	!Corresponding to P.
     1            + FP(I).PPOW(1:NF)				!Thus, N = N/Q*P.
             RETURN			!That's all it takes! No multiplies nor divides!
            END IF		!So much for that fraction.
          END DO		!This relies on ALL(zero tests) yielding true, as when Q = 1.
          FRACTRAN = 0		!No hit.
        END FUNCTION FRACTRAN	!No massive multi-precision arithmetic!

        SUBROUTINE SHOWN(S,F)	!Service routine to show the state after a step is calculated.
Could imaging a function I6FMT(23) that returns "    23" and "      " for non-positive numbers.
Can't do it, as if this were invoked via a WRITE statement, re-entrant use of WRITE usually fails.
         INTEGER S,F	!Step number, Fraction number.
         INTEGER I	!A stepper.
         CHARACTER*(9+4+1 + NL*6) ALINE	!A scratchpad matching FORMAT 103.
          WRITE (ALINE,103) S,F,NPPOW(PLIVE(1:NL))	!Show it!
  103     FORMAT (I9,I4,":",<NL>I6)	!As a sequence of powers of primes.
          IF (F.LE.0) ALINE(10:13) = ""	!Scrub when no fraction is fingered.
          DO I = 1,NL		!Step along the live primes.
            IF (NPPOW(PLIVE(I)).GT.0) CYCLE	!Ignoring the empowered ones.
            ALINE(15 + (I - 1)*6:14 + I*6) = ""	!Blank out zero powers.
          END DO		!On to the next.
          WRITE (MSG,"(A)") ALINE	!Reveal at last.
        END SUBROUTINE SHOWN	!A struggle.
      END MODULE CONWAYSIDEA	!Simple...

      PROGRAM POKE
      USE CONWAYSIDEA	!But, where does he get his ideas from?
      INTEGER P(ENUFF),Q(ENUFF)	!Holds the fractions as P(i)/Q(i).
      INTEGER N		!The working number.
      INTEGER LF	!Last fraction given.
      INTEGER LP	!Last prime needed.
      INTEGER MS	!Maximum number of steps.
      INTEGER I,IT	!Assistants.
      LOGICAL*1 PUSED(ENUFF)	!Track the usage of prime numbers,

      MSG = 6		!Standard output.
      WRITE (6,1)	!Announce.
    1 FORMAT ("Interpreter for J. H. Conway's FRACTRAN language.")

Chew into an example programme.
   10 OPEN (10,FILE = "Fractran.txt",STATUS="OLD",ACTION="READ")	!Rather than compiled-in stuff.
      READ (10,*) LF		!I need to know this without having to scan the input.
      WRITE (MSG,11) LF		!Reveal in case of trouble.
   11 FORMAT (I0," fractions, as follow:")	!Should the input evoke problems.
      READ (10,*)    (P(I),Q(I),I = 1,LF)	!Ask for the specified number of P,Q pairs.
      WRITE (MSG,12) (P(I),Q(I),I = 1,LF)	!Show what turned up.
   12 FORMAT (24(I0,"/",I0:", "))	!As P(i)/Q(i) pairs. The colon means that there will be no trailing comma.
      READ (10,*) N,MS			!The start value, and the step limit.
      CLOSE (10)			!Finished with input.
      WRITE (MSG,13) N,MS		!Hopefully, all went well.
   13 FORMAT ("Start with N = ",I0,", step limit ",I0)
      IF (.NOT.GRASPPRIMEBAG(66)) STOP "Gan't grab my file of primes!"	!Attempt in hope.

Convert the starting number to a more convenient form, an array of powers of successive prime numbers.
   20 FP(1) = FACTOR(N)		!Borrow one of the factor list variables.
      NPPOW = 0			!Clear all prime factor counts.
      DO I = 1,FP(1).PNUM(0)	!Now find what they are.
        NPPOW(FP(1).PNUM(I)) = FP(1).PPOW(I)	!Convert from a variable-length list
      END DO			!To a fixed-length random-access array.
      PUSED = NPPOW.GT.0	!Note which primes have been used.
      LP = FP(1).PNUM(FP(1).PNUM(0))	!Recall the last prime required. More later.
Convert the supplied P(i)/Q(i) fractions to lists of prime number factors and powers in FP(i) and FQ(i).
      DO I = 1,LF	!Step through the fractions.
        IT = GCD(P(I),Q(I))	!Suspicion.
        IF (IT.GT.1) THEN	!Justified?
          WRITE (MSG,21) I,P(I),Q(I),IT	!Alas. Complain. The rule is N*(P/Q) being integer.
   21     FORMAT ("Fraction ",I3,", ",I0,"/",I0,!N*6/3 is integer always because this is N*2/1, but 3 may not divide N.
     1     " has common factor ",I0,"!")	!By removing IT,
          P(I) = P(I)/IT			!The test need merely check if N is divisible by Q.
          Q(I) = Q(I)/IT			!And, as N is factorised in NPPOW
        END IF					!And Q in FQ, subtractions of powers only is needed.
        FP(I) = FACTOR(P(I))		!Righto, form the factor list for P.
        PUSED(FP(I).PNUM(1:FP(I).PNUM(0))) = .TRUE.	!Mark which primes it fingers.
        LP = MAX(LP,FP(I).PNUM(FP(I).PNUM(0)))		!One has no prime factors: PNUM(0) = 0.
        FQ(I) = FACTOR(Q(I))		!And likewise for Q.
        PUSED(FQ(I).PNUM(1:FQ(I).PNUM(0))) = .TRUE.	!Some primes may be omitted.
        LP = MAX(LP,FQ(I).PNUM(FQ(I).PNUM(0)))		!If no prime factors, PNUM(0) fingers element zero, which is zero.
      END DO		!All this messing about saves on multiplication and division.
Check which primes are in use, preparing an index of live primes..
      NL = 0		!No live primes.
      DO I = 1,LP	!Check up to the last prime.
        IF (PUSED(I)) THEN	!This one used?
          NL = NL + 1		!Yes. Another.
          PLIVE(NL) = I		!Fingered.
        END IF		!So much for that prime.
      END DO		!On to the next.
      WRITE (MSG,22) NL,LP,PRIME(LP)	!Remark on usage.
   22 FORMAT ("Require ",I0," primes only, up to Prime(",I0,") = ",I0)	!Presume always more than one prime.
      IF (LP.GT.LASTP) STOP "But, that's too many for array NPPOW!"

Cast forth a heading.
  100 WRITE (MSG,101) (PRIME(PLIVE(I)), I = 1,NL)	!Splat a heading.
  101 FORMAT (/,14X,"N as powers of prime factors",/,	!The prime heading,
     1 5X,"Step  F#:",<LP>I6)		!With primes beneath.
      CALL SHOWN(0,0)	!Initial state of N as NPPOW. Step zero, no fraction.

Commence!
      DO I = 1,MS	!Here we go!
        IT = FRACTRAN(LF)	!Do it!
        CALL SHOWN(I,IT)	!Show it!
        IF (IT.LE.0) EXIT	!Quit it?
      END DO		!The next step.
Complete!
      END	!Whee!

Revised Results

Edited in are >>> markers for the prime powers of two.

Interpreter for J. H. Conway's FRACTRAN language.
14 fractions, as follow:
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
Start with N = 2, step limit 100
Require 10 primes only, up to Prime(10) = 29

              N as powers of prime factors
     Step  F#:     2     3     5     7    11    13    17    19    23    29
        0    :     1
        1  13:           1     1
        2  14:           1     2           1
        3   5:                 2                                         1
        4   6:                 2     1     1
        5  11:                 2     1           1
        6   1:                 2                       1
        7   2:     1     1     1                 1
        8  10:     1     1     1           1
        9   5:     1           1                                         1
       10   6:     1           1     1     1
       11  11:     1           1     1           1
       12   1:     1           1                       1
       13   2:     2     1                       1
       14  10:     2     1                 1
       15   5:     2                                                     1
       16   6:     2                 1     1
       17  11:     2                 1           1
       18   1:     2                                   1
  >>>  19   9:     2
       20  13:     1     1     1
       21  13:           2     2
       22  14:           2     3           1
       23   5:           1     3                                         1
       24   6:           1     3     1     1
       25   5:                 3     1                                   1
       26   6:                 3     2     1
       27  11:                 3     2           1
       28   1:                 3     1                 1
       29   2:     1     1     2     1           1
       30   1:     1     1     2                       1
       31   2:     2     2     1                 1
       32  10:     2     2     1           1
       33   5:     2     1     1                                         1
       34   6:     2     1     1     1     1
       35   5:     2           1     1                                   1
       36   6:     2           1     2     1
       37  11:     2           1     2           1
       38   1:     2           1     1                 1
       39   2:     3     1           1           1
       40   1:     3     1                             1
       41   3:     3                                         1
       42   4:     2                                               1
       43   7:     2           1                             1
       44   4:     1           1                                   1
       45   7:     1           2                             1
       46   4:                 2                                   1
       47   7:                 3                             1
       48   8:                 3     1     1
       49  11:                 3     1           1
       50   1:                 3                       1
       51   2:     1     1     2                 1
       52  10:     1     1     2           1
       53   5:     1           2                                         1
       54   6:     1           2     1     1
       55  11:     1           2     1           1
       56   1:     1           2                       1
       57   2:     2     1     1                 1
       58  10:     2     1     1           1
       59   5:     2           1                                         1
       60   6:     2           1     1     1
       61  11:     2           1     1           1
       62   1:     2           1                       1
       63   2:     3     1                       1
       64  10:     3     1                 1
       65   5:     3                                                     1
       66   6:     3                 1     1
       67  11:     3                 1           1
       68   1:     3                                   1
  >>>  69   9:     3
       70  13:     2     1     1
       71  13:     1     2     2
       72  13:           3     3
       73  14:           3     4           1
       74   5:           2     4                                         1
       75   6:           2     4     1     1
       76   5:           1     4     1                                   1
       77   6:           1     4     2     1
       78   5:                 4     2                                   1
       79   6:                 4     3     1
       80  11:                 4     3           1
       81   1:                 4     2                 1
       82   2:     1     1     3     2           1
       83   1:     1     1     3     1                 1
       84   2:     2     2     2     1           1
       85   1:     2     2     2                       1
       86   2:     3     3     1                 1
       87  10:     3     3     1           1
       88   5:     3     2     1                                         1
       89   6:     3     2     1     1     1
       90   5:     3     1     1     1                                   1
       91   6:     3     1     1     2     1
       92   5:     3           1     2                                   1
       93   6:     3           1     3     1
       94  11:     3           1     3           1
       95   1:     3           1     2                 1
       96   2:     4     1           2           1
       97   1:     4     1           1                 1
       98   3:     4                 1                       1
       99   4:     3                 1                             1
      100   7:     3           1     1                       1

This time, restricting output to only occasions when N is a power of two requires no peculiar bit-counting function. Just change the interpretation loop to

      DO I = 1,MS	!Here we go!
        IT = FRACTRAN(LF)	!Do it!
        IF (ALL(NPPOW(2:LP).EQ.0)) CALL SHOWN(I,IT)	!Show it!
        IF (IT.LE.0) EXIT	!Quit it?
      END DO		!The next step.

Output:

Interpreter for J. H. Conway's FRACTRAN language.
14 fractions, as follow:
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
Start with N = 2, step limit 6666666
Require 10 primes only, up to Prime(10) = 29

              N as powers of prime factors
     Step  F#:     2     3     5     7    11    13    17    19    23    29
        0    :     1
       19   9:     2
       69   9:     3
      280   9:     5
      707   9:     7
     2363   9:    11
     3876   9:    13
     8068   9:    17
    11319   9:    19
    19201   9:    23
    36866   9:    29
    45551   9:    31
    75224   9:    37
   101112   9:    41
   117831   9:    43
   152025   9:    47
   215384   9:    53
   293375   9:    59
   327020   9:    61
   428553   9:    67
   507519   9:    71
   555694   9:    73
   700063   9:    79
   808331   9:    83
   989526   9:    89
  1273490   9:    97
  1434366   9:   101
  1530213   9:   103
  1710923   9:   107
  1818254   9:   109
  2019962   9:   113
  2833089   9:   127
  3104685   9:   131
  3546320   9:   137
  3720785   9:   139
  4549718   9:   149
  4755581   9:   151
  5329874   9:   157
  5958403   9:   163
  6400897   9:   167

Execution took about two seconds.

Add and Multiply

Examples taken from Wikipaedia...

Interpreter for J. H. Conway's FRACTRAN language.
1 fraction, as follows:
3/2
Start with N = 72, step limit 66
Require 2 primes only, up to Prime(2) = 3

              N as powers of prime factors
     Step  F#:     2     3
        0    :     3     2
        1   1:     2     3
        2   1:     1     4
        3   1:           5
        4    :           5

The initial value is 72 = 2³x3² so that "register" two holds 3 and register three holds 2. On completion, register three holds 5, the sum of 2 and 3.

Interpreter for J. H. Conway's FRACTRAN language.
6 fractions, as follow:
455/33, 11/13, 1/11, 3/7, 11/2, 1/3
Start with N = 72, step limit 66
Require 6 primes only, up to Prime(6) = 13

              N as powers of prime factors
     Step  F#:     2     3     5     7    11    13
        0    :     3     2
        1   5:     2     2                 1
        2   1:     2     1     1     1           1
        3   2:     2     1     1     1     1
        4   1:     2           2     2           1
        5   2:     2           2     2     1
        6   3:     2           2     2
        7   4:     2     1     2     1
        8   4:     2     2     2
        9   5:     1     2     2           1
       10   1:     1     1     3     1           1
       11   2:     1     1     3     1     1
       12   1:     1           4     2           1
       13   2:     1           4     2     1
       14   3:     1           4     2
       15   4:     1     1     4     1
       16   4:     1     2     4
       17   5:           2     4           1
       18   1:           1     5     1           1
       19   2:           1     5     1     1
       20   1:                 6     2           1
       21   2:                 6     2     1
       22   3:                 6     2
       23   4:           1     6     1
       24   4:           2     6
       25   6:           1     6
       26   6:                 6
       27    :                 6

Here, register two holds 3 and register three holds 2. Their product appears in register five.

FreeBASIC

Added a compiler condition to make the program work with the old GMP.bi header file

' version 06-07-2015
' compile with: fbc -s console
' uses gmp

#Include Once "gmp.bi"

' in case the two #define's are missing from 'gmp.bi' define them now
#Ifndef mpq_numref
    #Define mpq_numref(Q) (@(Q)->_mp_num)
    #Define mpq_denref(Q) (@(Q)->_mp_den)
#EndIf

Dim As String prog(0 To ...) = {"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"}

Dim As UInteger i, j, c, max = UBound(prog)
Dim As Integer scanbit

Dim As ZString Ptr gmp_str : gmp_str = Allocate(10000)
Dim As Mpq_ptr  in_, out_
in_ = Allocate(Len(__mpq_struct)) : Mpq_init(in_)
out_ = Allocate(Len(__mpq_struct)) : Mpq_init(out_)
Dim As mpz_ptr num, den
num = Allocate(Len(__mpz_struct)) : Mpz_init(num)
den = Allocate(Len(__mpz_struct)) : Mpz_init(den)

Dim As mpq_ptr instruction(max)
For i = 0 To max
    instruction(i) = Allocate(Len(__mpq_struct))
    mpq_init(instruction(i))
    mpq_set_str(instruction(i), prog(i), 10 )
Next

mpq_set_str(in_ ,"2",10)
i = 0 : j = 0
Print "2";
Do
    mpq_mul(out_, instruction(i), in_)
    i = i + 1
    den = mpq_denref(out_)
    If mpz_cmp_ui(den, 1) = 0 Then
        Mpq_get_str(gmp_str, 10, out_)
        Print ", ";*gmp_str;
        mpq_swap(in_, out_)
        i = 0
        j = j + 1
    End If
Loop Until j > 14

' this one only display if the integer is 2^p, p being prime
mpq_set_str(in_ ,"2",10)
i = 0 : j = 0 : c = 0
Print : Print : Print
Print "count          iterations    prime  2^prime"

Do
    mpq_mul(out_, instruction(i), in_)
    i = i + 1
    j = j + 1
    den = mpq_denref(out_)
    If mpz_cmp_ui(den, 1) = 0 Then
        num = mpq_numref(out_)
        scanbit =  mpz_scan1(num, 0)
        ' if scanbit = 0 then number is odd
        If scanbit > 0 Then
            ' return from mpz_scan1(num, scanbit+1) is -1 for power of 2
            If mpz_scan1(num, scanbit +1) = -1 Then
                If c <= 20 Then Mpq_get_str(gmp_str, 10, out_) Else *gmp_str = ""
                c = c + 1
                Print Using "##### ################### ########  "; c; j; scanbit;
                Print *gmp_str
                If InKey <> "" Then Exit Do
            End If
        End If
        mpq_swap(in_, out_)
        i = 0
    End If
Loop

' Loop Until scanbit > 300
' Loop Until InKey <> ""
' Loop Until scanbit > 300 Or InKey <> ""
' stopping conditions will slow down the hole loop
' loop will check for key if it's printing a result

' empty keyboard buffer
While InKey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End

Output:

2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116

count          iterations    prime  2^prime
    1                 129        2  4
    2                 425        3  8
    3                1563        5  32
    4                3735        7  128
    5               11674       11  2048
    6               18811       13  8192
    7               38010       17  131072
    8               52854       19  524288
    9               88134       23  8388608
   10              166070       29  536870912
   11              204575       31  2147483648
   12              333931       37  137438953472
   13              446506       41  2199023255552
   14              519556       43  8796093022208
   15              667496       47  140737488355328
   16              940183       53  9007199254740992
   17             1274660       59  576460752303423488
   18             1419935       61  2305843009213693952
   19             1853979       67  147573952589676412928
   20             2191673       71  2361183241434822606848
shorten output file
   42            34533967      181  
   43            40326168      191

Fōrmulæ

Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.

Programs in Fōrmulæ are created/edited online in its website.

In this page you can see and run the program(s) related to this task and their results. You can also change either the programs or the parameters they are called with, for experimentation, but remember that these programs were created with the main purpose of showing a clear solution of the task, and they generally lack any kind of validation.

Solution

It is a function that accepts the program to run (as a list), the initial value of n and the number of values to generate.

It uses a local nested function next() that calculates the next value of . If it can be calculated, it is added to a result array and return true, elsewhere return false.

The main work is to iterate while the next() returns true and the number of values to generate is not reached.

The following is the call with the program for primes, initial n value of 2, and returning 20 values:

Bonus using the previous FRACTAN program to generate the first 20 primes.

It requires a modification to the previous program.

FRACTRAN program for addition

FRACTRAN program for multiplication

Go

Basic task: This compiles to produce a program that reads the limit, starting number n, and list of fractions as command line arguments, with the list of fractions as a single argument.

package main

import (
    "fmt"
    "log"
    "math/big"
    "os"
    "strconv"
    "strings"
)

func compile(src string) ([]big.Rat, bool) {
    s := strings.Fields(src)
    r := make([]big.Rat, len(s))
    for i, s1 := range s {
        if _, ok := r[i].SetString(s1); !ok {
            return nil, false
        }
    }
    return r, true
}

func exec(p []big.Rat, n *big.Int, limit int) {
    var q, r big.Int
rule:
    for i := 0; i < limit; i++ {
        fmt.Printf("%d ", n)
        for j := range p {
            q.QuoRem(n, p[j].Denom(), &r)
            if r.BitLen() == 0 {
                n.Mul(&q, p[j].Num())
                continue rule
            }
        }
        break
    }
    fmt.Println()
}

func usage() {
    log.Fatal("usage: ft <limit> <n> <prog>")
}

func main() {
    if len(os.Args) != 4 {
        usage()
    }
    limit, err := strconv.Atoi(os.Args[1])
    if err != nil {
        usage()
    }
    var n big.Int
    _, ok := n.SetString(os.Args[2], 10)
    if !ok {
        usage()
    }
    p, ok := compile(os.Args[3])
    if !ok {
        usage()
    }
    exec(p, &n, limit)
}

Command line usage, with program compiled as "ft":

> ft 15 2 "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"
2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132

Extra credit: This invokes above program with appropriate arguments, and processes the output to obtain the 20 primes.

package main

import (
    "fmt"
    "log"
    "math/big"
    "os"
    "os/exec"
)

func main() {
    c := exec.Command("ft", "1000000", "2", `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`)
    c.Stderr = os.Stderr
    r, err := c.StdoutPipe()
    if err != nil {
        log.Fatal(err)
    }
    if err = c.Start(); err != nil {
        log.Fatal(err)
    }
    var n big.Int
    for primes := 0; primes < 20; {
        if _, err = fmt.Fscan(r, &n); err != nil {
            log.Fatal(err)
        }
        l := n.BitLen() - 1
        n.SetBit(&n, l, 0)
        if n.BitLen() == 0 && l > 1 {
            fmt.Printf("%d ", l)
            primes++
        }
    }
    fmt.Println()
}

Output:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71

Haskell

Running the program

import Data.List (find)
import Data.Ratio (Ratio, (%), denominator)

fractran :: (Integral a) => [Ratio a] -> a -> [a]
fractran fracts n = n :
  case find (\f -> n `mod` denominator f == 0) fracts of
    Nothing -> []
    Just f -> fractran fracts $ truncate (fromIntegral n * f)

Example:

λ> let prog = [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]

λ> take 15 $ fractran prog 2
[2,15,825,725,1925,2275,425,390,330,290,770,910,170,156,132]

Reading the program

Additional import

import Data.List.Split (splitOn)

readProgram :: String -> [Ratio Int]
readProgram = map (toFrac . splitOn "/") . splitOn ","
  where toFrac [n,d] = read n % read d

Example of running the program:

λ> let prog = readProgram "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"

λ> take 15 $ fractran prog 2
[2,15,825,725,1925,2275,425,390,330,290,770,910,170,156,132]

Generation of primes

Additional import

import Data.Maybe (mapMaybe)
import Data.List (elemIndex)

primes :: [Int]
primes = mapMaybe log2 $ fractran prog 2
  where
    prog =
      [ 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
      ]
    log2 = fmap succ . elemIndex 2 . takeWhile even . iterate (`div` 2)

λ> take 20 primes
[1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67]

Icon and Unicon

Works in both languages:

record fract(n,d)

procedure main(A)
    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", 2)
end

procedure fractran(s, n, limit)
    execute(parse(s),n, limit)
end

procedure parse(s)
    f := []
    s ? while not pos(0) do {
            tab(upto(' ')|0) ? put(f,fract(tab(upto('/')), (move(1),tab(0))))
            move(1)
            }
    return f
end

procedure execute(f,d,limit)
     /limit := 15
     every !limit do {
         if d := (d%f[i := !*f].d == 0, (writes(" ",d)/f[i].d)*f[i].n) then {}
         else break write()
         }
     write()
end

Output:

->fractan
 2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132
->

J

Hybrid version

Solution:

toFrac=: '/r' 0&".@charsub ]                           NB. read fractions from string
fractran15=: ({~ (= <.) i. 1:)@(toFrac@[ * ]) ^:(<15)  NB. return first 15 Fractran results

Example:

   taskstr=: '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'
   taskstr fractran15 2
2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132

Tacit version

Solution

This is a variation of the previous solution which it is not entirely tacit due to the use of the explicit standard library verb (function) charsub. The adverb (functional) fractran is defined as a fixed tacit adverb (that is, a stateless point-free functional),

fractran=. (((({~ (1 i.~ (= <.)))@:* ::]^:)(`]))(".@:('1234567890r ' {~ '1234567890/ '&i.)@:[`))(`:6)

The argument of fractran specifies a limit for the number of steps; if the limit is boxed the intermediate results are also included in the result.

Example

   '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' (<15) fractran 2
2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132

Extra credit

The prime numbers are produced via the adverb primes; its argument has the same specifications as the argument for the fractran adverb (which is used in its definition),

primes=. ('fractan'f.) ((1 }. 2 ^. (#~ *./@:e.&2 0"1@:q:))@:)
   
   '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' (<555555) primes 2
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71

primes is also a stateless point-free functional,

   primes
((((({~ (1 i.~ (= <.)))@:* ::]^:)(`]))(".@:('1234567890r ' {~ '1234567890/ '&i.)@:[`))(`:6))((1 }. 2 ^. (#~ *./@:e.&2 0"1@:q:))@:)

Turing completeness of J's stateless point-free dialect

When _ is the limit argument (i.e., when no limit is imposed) the run will halt according to the FRACTRAN programming language specifications (the run might also be forced to halt if a trivial changeless single cycle, induced by a useless 1/1 fraction, is detected). Thus, the FRACTRAN associated verb (function) is,

   _ fractran
".@:('1234567890r ' {~ '1234567890/ '&i.)@:[ ({~ (1 i.~ (= <.)))@:* ::]^:_ ]

Actually, most of the code above is there to comply with the task's requirement of a "natural format." When J's format for fractions is used the FRACTRAN verb becomes,

FRACTRAN=. ({~ (1 i.~ (= <.)))@:* ::]^:_

which is an indirect concise confirmation that J's fixed tacit dialect is Turing complete.

In the following example, FRACTRAN calculates the product 4 * 6, the initial value 11664 = (2^4)*(3^6) holds 4 in the register associated with 2 and holds 6 in the register associated with 3; the result 59604644775390625 = 5^24 holds the product 24 = 4 * 6 in the register associated with 5,

   455r33 11r13 1r11 3r7 11r2 1r3 FRACTRAN 11664
59604644775390625

Java

import java.util.Vector;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Fractran{

   public static void main(String []args){ 

       new 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", 2);
   }
   final int limit = 15;
   

   Vector<Integer> num = new Vector<>(); 
   Vector<Integer> den = new Vector<>(); 
   public Fractran(String prog, Integer val){
      compile(prog);
      dump();
      exec(2);
    }


   void compile(String prog){
      Pattern regexp = Pattern.compile("\\s*(\\d*)\\s*\\/\\s*(\\d*)\\s*(.*)");
      Matcher matcher = regexp.matcher(prog);
      while(matcher.find()){
         num.add(Integer.parseInt(matcher.group(1)));
         den.add(Integer.parseInt(matcher.group(2)));
         matcher = regexp.matcher(matcher.group(3));
      }
   }

   void exec(Integer val){
       int n = 0;
       while(val != null && n<limit){
           System.out.println(n+": "+val);
           val = step(val);
           n++;
       }
   }
   Integer step(int val){
       int i=0; 
       while(i<den.size() && val%den.get(i) != 0) i++;
       if(i<den.size())
           return num.get(i)*val/den.get(i);
       return null;
   }

   void dump(){
       for(int i=0; i<den.size(); i++)
           System.out.print(num.get(i)+"/"+den.get(i)+" ");
       System.out.println();
   }
}

JavaScript

Imperative

// Parses the input string for the numerators and denominators
function compile(prog, numArr, denArr) {
    let regex = /\s*(\d*)\s*\/\s*(\d*)\s*(.*)/m;
    let result;
    while (result = regex.exec(prog)) {
        numArr.push(result[1]);
        denArr.push(result[2]);
        prog = result[3];
    }
    return [numArr, denArr];
}

// Outputs the result of the compile stage
function dump(numArr, denArr) {
    let output = "";
    for (let i in numArr) {
        output += `${numArr[i]}/${denArr[i]} `;
    }
    return `${output}<br>`;
}

// Step
function step(val, numArr, denArr) {
    let i = 0;
    while (i < denArr.length && val % denArr[i] != 0) i++;
    return numArr[i] * val / denArr[i];
}

// Executes Fractran
function exec(val, i, limit, numArr, denArr) {
    let output = "";
    while (val && i < limit) {
        output += `${i}: ${val}<br>`;
        val = step(val, numArr, denArr);
        i++;
    }
    return output;
}

// Main
// Outputs to DOM (clears and writes at the body tag)
let body = document.body;
let [num, den] = compile("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", [], []);
body.innerHTML = dump(num, den);
body.innerHTML += exec(2, 0, 15, num, den);

Functional

Translation of: Haskell

Here is a functionally composed version, which also derives a few primes. I may have missed something, but this first draft suggests that we may need bigInt support (which JS lacks) to get as far as the sixth prime.

(() => {
    'use strict';

    // fractran :: [Ratio Int] -> Int -> Gen [Int]
    const fractran = (xs, n) => {
        function* go(n) {
            const p = r => 0 === v % r.d;
            let
                v = n,
                mb = find(p, xs);
            yield v
            while (!mb.Nothing) {
                mb = bindMay(
                    find(p, xs),
                    r => (
                        v = truncate({
                            type: 'Ratio',
                            n: v * r.n,
                            d: r.d
                        }),
                        Just(v)
                    )
                );
                mb.Just && (yield v)
            }
        };
        return go(n);
    };

    // readRatios :: String -> [Ratio]
    const readRatios = s =>
        map(x => ratio(...map(read, splitOn('/', x))),
            splitOn(',', s)
        );

    // main :: IO()
    const main = () => {

        // strRatios :: String
        const strRatios = `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`;

        showLog(
            'First fifteen steps:',
            take(15,
                fractran(readRatios(strRatios), 2)
            )
        );

        showLog(
            'First five primes:',
            take(5,
                mapMaybeGen(
                    x => fmapMay(
                        succ,
                        elemIndex(
                            2,
                            takeWhileGen(
                                even,
                                iterate(n => div(n, 2), x)
                            )
                        )
                    ),
                    fractran(readRatios(strRatios), 2)
                )
            )
        );
    };

    // GENERIC ABSTRACTIONS ----------------------------

    // Just :: a -> Maybe a
    const Just = x => ({
        type: 'Maybe',
        Nothing: false,
        Just: x
    });

    // Nothing :: Maybe a
    const Nothing = () => ({
        type: 'Maybe',
        Nothing: true,
    });

    // Tuple (,) :: a -> b -> (a, b)
    const Tuple = (a, b) => ({
        type: 'Tuple',
        '0': a,
        '1': b,
        length: 2
    });

    // abs :: Num -> Num
    const abs = Math.abs;

    // bindMay (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
    const bindMay = (mb, mf) =>
        mb.Nothing ? mb : mf(mb.Just);

    // div :: Int -> Int -> Int
    const div = (x, y) => Math.floor(x / y);

    // elemIndex :: Eq a => a -> [a] -> Maybe Int
    const elemIndex = (x, xs) => {
        const i = xs.indexOf(x);
        return -1 === i ? (
            Nothing()
        ) : Just(i);
    };

    // even :: Int -> Bool
    const even = n => 0 === n % 2;

    // find :: (a -> Bool) -> [a] -> Maybe a
    const find = (p, xs) => {
        for (let i = 0, lng = xs.length; i < lng; i++) {
            if (p(xs[i])) return Just(xs[i]);
        }
        return Nothing();
    };

    // fmapMay (<$>) :: (a -> b) -> Maybe a -> Maybe b
    const fmapMay = (f, mb) =>
        mb.Nothing ? (
            mb
        ) : Just(f(mb.Just));

    // foldl :: (a -> b -> a) -> a -> [b] -> a
    const foldl = (f, a, xs) => xs.reduce(f, a);

    // gcd :: Int -> Int -> Int
    const gcd = (x, y) => {
        const
            _gcd = (a, b) => (0 === b ? a : _gcd(b, a % b)),
            abs = Math.abs;
        return _gcd(abs(x), abs(y));
    };

    // iterate :: (a -> a) -> a -> Gen [a]
    function* iterate(f, x) {
        let v = x;
        while (true) {
            yield(v);
            v = f(v);
        }
    }

    // map :: (a -> b) -> [a] -> [b]
    const map = (f, xs) => xs.map(f);

    // mapMaybeGen :: (a -> Maybe b) -> Gen [a] -> [b]
    function* mapMaybeGen(mf, gen) {
        let v = take(1, gen);
        while (0 < v.length) {
            let mb = mf(v[0]);
            if (!mb.Nothing) yield mb.Just
            v = take(1, gen);
        }
    }

    // properFracRatio :: Ratio -> (Int, Ratio)
    const properFracRatio = nd => {
        const [q, r] = Array.from(quotRem(nd.n, nd.d));
        return Tuple(q, ratio(r, nd.d));
    };

    // quot :: Int -> Int -> Int
    const quot = (n, m) => Math.floor(n / m);

    // quotRem :: Int -> Int -> (Int, Int)
    const quotRem = (m, n) =>
        Tuple(Math.floor(m / n), m % n);

    // ratio :: Int -> Int -> Ratio Int
    const ratio = (n, d) =>
        0 !== d ? (() => {
            const g = gcd(n, d);
            return {
                type: 'Ratio',
                'n': quot(n, g), // numerator
                'd': quot(d, g) // denominator
            }
        })() : undefined;

    // read :: Read a => String -> a
    const read = JSON.parse;

    // showLog :: a -> IO ()
    const showLog = (...args) =>
        console.log(
            args
            .map(JSON.stringify)
            .join(' -> ')
        );

    // snd :: (a, b) -> b
    const snd = tpl => tpl[1];

    // splitOn :: [a] -> [a] -> [[a]]
    // splitOn :: String -> String -> [String]
    const splitOn = (pat, src) =>
        src.split(pat);

    // succ :: Int -> Int
    const succ = x =>
        1 + x;

    // take :: Int -> [a] -> [a]
    // take :: Int -> String -> String
    const take = (n, xs) =>
        xs.constructor.constructor.name !== 'GeneratorFunction' ? (
            xs.slice(0, n)
        ) : [].concat.apply([], Array.from({
            length: n
        }, () => {
            const x = xs.next();
            return x.done ? [] : [x.value];
        }));

    // takeWhileGen :: (a -> Bool) -> Gen [a] -> [a]
    const takeWhileGen = (p, xs) => {
        const ys = [];
        let
            nxt = xs.next(),
            v = nxt.value;
        while (!nxt.done && p(v)) {
            ys.push(v);
            nxt = xs.next();
            v = nxt.value
        }
        return ys;
    };

    // truncate :: Num -> Int
    const truncate = x =>
        'Ratio' === x.type ? (
            properFracRatio(x)[0]
        ) : properFraction(x)[0];

    // MAIN ---
    return main();
})();

Output:

"First fifteen steps:" -> [2,15,825,725,1925,2275,425,390,330,290,770,910,170,156,132]
"First five primes:" -> [1,2,3,5,7]

Julia

Works with: Julia version 1.9

# FRACTRAN interpreter implemented as an iterable struct

using .Iterators: filter, map, take

struct Fractran
    rs::Vector{Rational{BigInt}}
    i₀::BigInt
    limit::Int
end

Base.iterate(f::Fractran, i = f.i₀) =
    for r in f.rs
        if iszero(i % r.den)
            i = i ÷ r.den * r.num
            return i, i
        end
    end

interpret(f::Fractran) = 
    take(
        map(trailing_zeros,
            filter(ispow2, f))
        f.limit)

Base.show(io::IO, f::Fractran) =
    join(io, interpret(f), ' ')

macro code_str(s)
   [eval(Meta.parse(replace(t, "/" => "//"))) for t ∈ split(s)]
end

primes = Fractran(code"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", 2, 30)

# Output
println("First 25 iterations of FRACTRAN program 'primes':\n2 ",
    join(take(primes, 25), ' '))

println("\nWatch the first 30 primes dropping out within seconds:")

primes

Output:

First 25 iterations of FRACTRAN program 'primes':
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

Watch the first 30 primes dropping out within seconds:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113

Kotlin

// version 1.1.3

import java.math.BigInteger

class Fraction(val num: BigInteger, val denom: BigInteger) {
    operator fun times(n: BigInteger) = Fraction (n * num, denom)

    fun isIntegral() = num % denom == BigInteger.ZERO
}

fun String.toFraction(): Fraction {
    val split = this.split('/')
    return Fraction(BigInteger(split[0]), BigInteger(split[1]))
}

val BigInteger.isPowerOfTwo get() = this.and(this - BigInteger.ONE) == BigInteger.ZERO

val log2 = Math.log(2.0)

fun fractran(program: String, n: Int, limit: Int, primesOnly: Boolean): List<Int> {
    val fractions = program.split(' ').map { it.toFraction() }
    val results = mutableListOf<Int>()
    if (!primesOnly) results.add(n)
    var nn = BigInteger.valueOf(n.toLong())
    while (results.size < limit) {
        val frac = fractions.find { (it * nn).isIntegral() } ?: break
        nn = nn * frac.num / frac.denom
        if (!primesOnly) {
           results.add(nn.toInt())
        }
        else if (primesOnly && nn.isPowerOfTwo) {
           val prime = (Math.log(nn.toDouble()) / log2).toInt()
           results.add(prime)
        }
    }
    return results
}

fun main(args: Array<String>) {
    val program = "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"
    println("First twenty numbers:")
    println(fractran(program, 2, 20, false))
    println("\nFirst twenty primes:")
    println(fractran(program, 2, 20, true))
}

Output:

First twenty numbers:
[2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4]

First twenty primes:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

Mathematica / Wolfram Language

This isn't as efficient as possible for long lists of fractions, since it doesn't stop doing n*listelements once it finds an integer. Instead, it computes "is integer?" for n*{all list elements}. For short lists that's probably not a big deal.

fractionlist = {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};
n = 2;
steplimit = 20;
j = 0;
break = False;
While[break == False && j <= steplimit,
 newlist = n fractionlist;
 isintegerlist = IntegerQ[#] & /@ newlist; 
 truepositions = Position[isintegerlist, True];
 If[Length[truepositions] == 0,
  break = True,
  Print[ToString[j] <> ": " <> ToString[n]]; 
  n = newlist[[truepositions[[1, 1]]]]; j++;
  ]
 ]

Output:

Functional Version

Here is a different solution using a functional approach:

fractran[
  program : {__ ? (Element[#, PositiveRationals] &)},        (* list of positive fractions *)
  n0_Integer,                                                (* initial state *)
  maxSteps : _Integer : Infinity] :=                         (* max number of steps *)
 NestWhileList[                                              (* Return a list representing the evolution of the state n *)
  Function[n, SelectFirst[IntegerQ][program * n]],           (* Select first integer in n*program, if none return Missing *)
  n0,
  Not @* MissingQ,                                           (* continue while the state is not Missing *)
  1,
  maxSteps]

$PRIMEGAME = {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};
fractran[$PRIMEGAME, 2, 50]

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}

Extract the first 20 prime numbers encoded as powers of 2:

Select[IntegerQ] @ Log2[fractran[$PRIMEGAME, 2, 500000]]

Output:

{1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67}

Nim

Using fractions

Library: bignum

This is a simple implementation which operates on fractions. As Nim standard library doesn’t provide a module for big numbers, we have used the extra library “bignum” which relies on “gmp”. We provide a general function to run any Fractran program and a specialized iterator to find prime numbers.

import strutils
import bignum

const PrimeProg = "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"

iterator values(prog: openArray[Rat]; init: Natural): Int =
  ## Run the program "prog" with initial value "init" and yield the values.
  var n = newInt(init)
  var next: Rat
  while true:
    for fraction in prog:
      next = n * fraction
      if next.denom == 1:
        break
    n = next.num
    yield n

func toFractions(fractList: string): seq[Rat] =
  ## Convert a string to a list of fractions.
  for f in fractList.split():
    result.add(newRat(f))

proc run(progStr: string; init: Natural; maxSteps: Natural = 0) =
  ## Run the program described by string "progStr" with initial value "init",
  ## stopping after "maxSteps" (0 means for ever).
  ## Display the value after each step.
  let prog = progStr.toFractions()
  var stepCount = 0
  for val in prog.values(init):
    inc stepCount
    echo stepCount, ": ", val
    if stepCount == maxSteps:
      break

iterator primes(n: Natural): int =
  # Yield the list of first "n" primes.
  let prog = PrimeProg.toFractions()
  var count = 0
  for val in prog.values(2):
    if isZero(val and (val - 1)):
      # This is a power of two.
      yield val.digits(2).int - 1   # Compute the exponent as number of binary digits minus one.
      inc count
      if count == n:
        break

# Run the program to compute primes displaying values at each step and stopping after 10 steps.
echo "First ten steps for program to find primes:"
PrimeProg.run(2, 10)

# Find the first 20 primes.
echo "\nFirst twenty prime numbers:"
for val in primes(20):
  echo val

Output:

First ten steps for program to find primes:
1: 15
2: 825
3: 725
4: 1925
5: 2275
6: 425
7: 390
8: 330
9: 290
10: 770

First twenty prime numbers:
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71

Using decomposition in prime factors

With this algorithm, we no longer need big numbers. To avoid overflow, value at each step is displayed using its decomposition in prime factors.

import algorithm
import sequtils
import strutils
import tables

const PrimeProg = "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"

type
  Fraction = tuple[num, denom: int]
  Factors = Table[int, int]
  FractranProg = object
    primes: seq[int]
    nums, denoms: seq[Factors]
    exponents: seq[int]   # Could also use a CountTable.

iterator fractions(fractString: string): Fraction =
  ## Extract fractions from a string and yield them.
  for f in fractString.split():
    let fields = f.strip().split('/')
    assert fields.len == 2
    yield (fields[0].parseInt(), fields[1].parseInt())

iterator factors(val: int): tuple[val, exp: int] =
  ## Extract factors from a positive integer.

  # Extract factor 2.
  var val = val
  var exp = 0
  while (val and 1) == 0:
    inc exp
    val = val shr 1
  if exp != 0:
    yield (2, exp)

  # Extract odd factors.
  var d = 3
  while d <= val:
    exp = 0
    while val mod d == 0:
      inc exp
      val = val div d
    if exp != 0:
      yield (d, exp)
    inc d, 2

func newProg(fractString: string; init: int): FractranProg =
  ## Initialize a Fractran program.

  for f in fractString.fractions():
    # Extract numerators factors.
    var facts: Factors
    for (val, exp) in f.num.factors():
      result.primes.add(val)
      facts[val] = exp
    result.nums.add(facts)
    # Extract denominator factors.
    facts.clear()
    for (val, exp) in f.denom.factors():
      result.primes.add(val)
      facts[val] = exp
    result.denoms.add(facts)

    # Finalize list of primes.
    result.primes.sort()
    result.primes = result.primes.deduplicate(true)

    # Allocate and initialize exponent sequence.
    result.exponents.setLen(result.primes[^1] + 1)
    for (val, exp) in init.factors():
      result.exponents[val] = exp

func doOneStep(prog: var FractranProg): bool =
  ## Execute one step of the program.

  for idx, factor in prog.denoms:
    block tryFraction:
      for val, exp in factor.pairs():
        if prog.exponents[val] < exp:
          # Not a multiple of the denominator.
          break tryFraction
      # Divide by the denominator.
      for val, exp in factor.pairs():
        dec prog.exponents[val], exp
      # Multiply by the numerator.
      for val, exp in prog.nums[idx]:
        inc prog.exponents[val], exp
      return true

func `$`(prog: FractranProg): string =
  ## Display a value as a product of prime factors.

  for val, exp in prog.exponents:
    if exp != 0:
      if result.len > 0:
        result.add('.')
      result.add($val)
      if exp > 1:
        result.add('^')
        result.add($exp)

proc run(fractString: string; init: int; maxSteps = 0) =
  ## Run a Fractran program.

  var prog = newProg(fractString, init)

  var stepCount = 0
  while stepCount < maxSteps:
    if not prog.doOneStep():
      echo "*** No more possible fraction. Program stopped."
      return
    inc stepCount
    echo stepCount, ": ", prog

proc findPrimes(maxCount: int) =
  ## Search and print primes.

  var prog = newProg(PrimeProg, 2)
  let oddPrimes = prog.primes[1..^1]
  var primeCount = 0
  while primeCount < maxCount:
    discard prog.doOneStep()
    block powerOf2:
      if prog.exponents[2] > 0:
        for p in oddPrimes:
          if prog.exponents[p] != 0:
            # Not a power of 2.
            break powerOf2
        inc primeCount
        echo primeCount, ": ", prog.exponents[2]

#------------------------------------------------------------------------------

echo "First ten steps for program to find primes:"
run(PrimeProg, 2, 10)
echo "\nFirst twenty prime numbers:"
findPrimes(20)

Output:

First ten steps for program to find primes:
1: 3.5
2: 3.5^2.11
3: 5^2.29
4: 5^2.7.11
5: 5^2.7.13
6: 5^2.17
7: 2.3.5.13
8: 2.3.5.11
9: 2.5.29
10: 2.5.7.11

First twenty prime numbers:
1: 2
2: 3
3: 5
4: 7
5: 11
6: 13
7: 17
8: 19
9: 23
10: 29
11: 31
12: 37
13: 41
14: 43
15: 47
16: 53
17: 59
18: 61
19: 67
20: 71

OCaml

This reads a Fractran program from standard input (keyboard or file) and runs it with the input given by the command line arguments, using arbitrary-precision numbers and fractions.

open Num

let get_input () =
   num_of_int (
     try int_of_string Sys.argv.(1)
     with _ -> 10)

let get_max_steps () =
   try int_of_string Sys.argv.(2)
   with _ -> 50
   
let read_program () =
   let line = read_line () in
   let words = Str.split (Str.regexp " +") line in
   List.map num_of_string words

let is_int n = n =/ (integer_num n)

let run_program num prog =

   let replace n =
      let rec step = function
      | [] -> None
      | h :: t ->
            let n' = h */ n in
            if is_int n' then Some n' else step t in
      step prog in

   let rec repeat m lim =
      Printf.printf "  %s\n" (string_of_num m);
      if lim = 0 then print_endline "Reached max step limit" else
         match replace m with
         | None -> print_endline "Finished"
         | Some x -> repeat x (lim-1)
   in

   let max_steps = get_max_steps () in
   repeat num max_steps

let () =
   let num = get_input () in
   let prog = read_program () in
   run_program num prog

The program

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

saved in a file can can be run with the command:

ocaml nums.cma str.cma fractran.ml 2 30 < primes.fct

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
Reached max step limit

PARI/GP

In this version ideas were borrowed from C++, Java and JavaScript.

Works with: PARI/GP version 2.7.4 and above

\\ FRACTRAN 
\\ 4/27/16 aev
fractran(val,ft,lim)={
my(ftn=#ft,fti,di,L=List(),j=0);
while(val&&j<lim, listput(L,val);
  for(i=1,ftn, fti=ft[i]; di=denominator(fti);
      if(val%di==0, break));\\fend i
  val= numerator(fti)*val/di; j++);\\wend j
return(Vec(L));
}

{\\ Executing:
my(v=[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]);
print(fractran(2,v,15));
}

Output:

[2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132]

Perl

Instead of printing all steps, I chose to only print those steps which were a power of two. This makes the fact that it's a prime-number-generating program much clearer.

use strict;
use warnings;
use Math::BigRat;

my ($n, @P) = map Math::BigRat->new($_), qw{
2 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
};

$|=1;
MAIN: for( 1 .. 5000 ) {
	print " " if $_ > 1;
	my ($pow, $rest) = (0, $n->copy);
	until( $rest->is_odd ) {
		++$pow;
		$rest->bdiv(2);
	}
	if( $rest->is_one ) {
		print "2**$pow";
	} else {
		#print $n;
	}
	for my $f_i (@P) {
		my $nf_i = $n * $f_i;
		next unless $nf_i->is_int;
		$n = $nf_i;
		next MAIN;
	}
	last;
}

print "\n";

If you uncomment the

#print $n

, it will print all the steps.

Phix

Using the same ideas as the Fortran entry (thanks!).

For example, suppose that known_factors happens to be {2,3,5}. [the exact order may vary]
2 is held as {1,0,0}, ie 2^1 * 3^0 * 5^0, and 15 as {0,1,1}, ie 2^0 * 3^1 * 5^1.

Notice that 2, being a power of 2, has zero in all slots other than 2.
We can say that (eg) 15 is not exactly divisible by 2 because an sq_sub({0,1,1},{1,0,0}) would contain some <0s.
We can also say that 15 is not a power of 2 because there are non-0 in other than n[find(2,known_factors)].
Division (to whole integer) is performed simply by subtracting the corresponding powers, as above not possible if any would be negative.

without js -- 8s
--with javascript_semantics -- 52s!! (see note)
constant steps = 20,
         primes = 45
 
sequence known_factors = {} -- nb: no specific order
 
function combine_factors(sequence n)
-- (inverse of as_primes)
    atom res = 1
    for i=1 to length(n) do
        if n[i]!=0 then
            res *= power(known_factors[i],n[i])
        end if
    end for
    return res
end function
 
function as_primes(integer n)
-- eg as_primes(55) -> {5,11} -> indexes to known_factors
    if n=1 then return {} end if
    sequence pf = prime_factors(n,duplicates:=true)
    sequence res = repeat(0,length(known_factors))
    for i=1 to length(pf) do
        integer k = find(pf[i],known_factors)
        if k=0 then
            known_factors = append(known_factors,pf[i])
            res = append(res,1)
        else
            res[k] += 1
        end if
    end for
--  atom chk = combine_factors(res)
--  if chk!=n then ?9/0 end if
    return res
end function
 
function parse(string s)
    sequence res = split(s)
    for i=1 to length(res) do
        sequence sri = scanf(res[i],"%d/%d")
        if length(sri)!=1 then ?9/0 end if  -- oops!
        integer {{n,d}} = sri
        res[i] = {as_primes(n),as_primes(d)}
    end for
    return res
end function
 
function step(sequence pgm, sequence n)
    for pc=1 to length(pgm) do
        sequence d = pgm[pc][2], res = n
--      sequence d = pgm[pc][2], res = deep_copy(n) -- (see timing note)
        bool ok = true
        for f=1 to length(d) do
            integer df = d[f]
            if df!=0 then
                if f>length(n) or df>n[f] then
                    ok = false
                    exit
                end if
                res[f] -= df
            end if
        end for
        if ok then
            n = pgm[pc][1]
            integer zf = length(n)-length(res)
            if zf>0 then res &= repeat(0,zf) end if
            for i=1 to length(n) do
                res[i] += n[i]
            end for
            return res
        end if
    end for
    return 0
end function
 
constant src = "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"
sequence pgm = parse(src)
object n = as_primes(2)
sequence res = {}
for i=1 to steps do
    n = step(pgm,n)
    if n=0 then exit end if
    res = append(res,combine_factors(n))
end for
printf(1,"first %d results: %v\n",{steps,res})
 
n = as_primes(2)
integer k2 = find(2,known_factors)
sequence n0 = repeat(0,length(known_factors))
res = {}
integer iteration = 1
atom t0 = time()
while length(res)<primes do
    n = step(pgm,n)
    if n=0 then exit end if
    n0[k2] = n[k2]
    if n=n0 then -- (ie all non-2 are 0)
        -- and the prime itself is ready and waiting...
        res = append(res,n[k2])
    end if
    iteration += 1
end while
printf(1,"first %d primes: %v\n",{primes,res})
printf(1,"%,d iterations in %s\n",{iteration,elapsed(time()-t0)})

Output:

first 20 results: {15,825,725,1925,2275,425,390,330,290,770,910,170,156,132,116,308,364,68,4,30}
first 45 primes: {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,
                  107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197}
10,494,775 iterations in 8.4s

For comparison with that 8.4s, I've collected Python: 386s, REXX: 60s for 25 (on tio, then it timed out), Ruby: 187s, Go: 1736s(!!), Julia 616s, FreeBasic 11.7s
(Clearly the algorithms being used are way more significant than any inherent programming language differences here.)
Update 17/01/2022: Also note that 8.4s is for desktop/Phix, without js. Adding with js and the required deep_copy() makes it about 6.5 times slower, though it actually fares somewhat better(/less awful) in a browser (30s vs 50s). Clearly the current hll implementation of deep_copy(), as first shipped in July 2021, is nowhere near as efficient as the older low-level "clone that must be avoided", at least not yet.

Prolog

load(Program, Fractions) :-
    re_split("[ ]+", Program, Split), odd_items(Split, TextualFractions),
    maplist(convert_frac, TextualFractions, Fractions).

odd_items(L, L) :- L = [_], !.  % remove the even elements from a list.
odd_items([X,_|L], [X|R]) :- odd_items(L, R).

convert_frac(Text, Frac) :-
    re_matchsub("([0-9]+)/([0-9]+)"/t, Text, Match, []),
    Frac is Match.1 rdiv Match.2.

step(_, [], stop) :- !.
step(N, [F|Fs], R) :-
    A is N*F,
    (integer(A) -> R = A; step(N, Fs, R)).

exec(Prg, Start, Lz) :-
    lazy_list(transition, Prg/Start, Lz).

transition(Prg/N0, Prg/N1, N1) :-
    step(N0, Prg, N1).

steps(K, Start, Prg, Seq) :-
    exec(Prg, Start, Values),
    length(Seq, K), Seq = [Start|Rest], prefix(Rest, Values), !.


% The actual PRIMEGEN program follows...

primegen(Prg) :-
    load("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", Prg).

primes(N, Primes) :-
    primegen(Prg), exec(Prg, 2, Steps),
    length(Primes, N), capture_primes(Primes, Steps).

capture_primes([], _) :- !.
capture_primes([P|Ps], [Q|Qs]) :- pow2(Q), !, P is lsb(Q), capture_primes(Ps, Qs).
capture_primes(Ps, [_|Qs]) :- capture_primes(Ps, Qs).

pow2(X) :- X /\ (X-1) =:= 0.

main :-
    primegen(Prg), steps(15, 2, Prg, Steps),
    format("The first 15 steps from PRIMEGEN are: ~w~n", [Steps]),
    primes(20, Primes),
    format("By running PRIMEGEN we found these primes: ~w~n", [Primes]),
    halt.

?- main.

Output:

The first 15 steps from PRIMEGEN are: [2,15,825,725,1925,2275,425,390,330,290,770,910,170,156,132]
By running PRIMEGEN we found these primes: [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71]

Python

Python: Generate series from a fractran program

from fractions import Fraction

def fractran(n, fstring='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'):
    flist = [Fraction(f) for f in fstring.replace(' ', '').split(',')]

    n = Fraction(n)
    while True:
        yield n.numerator
        for f in flist:
            if (n * f).denominator == 1:
                break
        else:
            break
        n *= f
    
if __name__ == '__main__':
    n, m = 2, 15
    print('First %i members of fractran(%i):\n  ' % (m, n) +
          ', '.join(str(f) for f,i in zip(fractran(n), range(m))))

Output:

First 15 members of fractran(2):
  2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132

Python: Generate primes

Use fractran above as a module imported into the following program.

from fractran import fractran

def fractran_primes():
    for i, fr in enumerate(fractran(2), 1):
        binstr = bin(fr)[2:]
        if binstr.count('1') == 1:
            prime = binstr.count('0')
            if prime > 1:   # Skip 2**0 and 2**1
                yield prime, i

if __name__ == '__main__':
    for (prime, i), j in zip(fractran_primes(), range(15)):
        print("Generated prime %2i from the %6i'th member of the fractran series" % (prime, i))

Output:

Generated prime  2 from the     20'th member of the fractran series
Generated prime  3 from the     70'th member of the fractran series
Generated prime  5 from the    281'th member of the fractran series
Generated prime  7 from the    708'th member of the fractran series
Generated prime 11 from the   2364'th member of the fractran series
Generated prime 13 from the   3877'th member of the fractran series
Generated prime 17 from the   8069'th member of the fractran series
Generated prime 19 from the  11320'th member of the fractran series
Generated prime 23 from the  19202'th member of the fractran series
Generated prime 29 from the  36867'th member of the fractran series
Generated prime 31 from the  45552'th member of the fractran series
Generated prime 37 from the  75225'th member of the fractran series
Generated prime 41 from the 101113'th member of the fractran series
Generated prime 43 from the 117832'th member of the fractran series
Generated prime 47 from the 152026'th member of the fractran series

Quackery

run performs the first step of executing a Fractran program, returning a rational number (represented as two stack items: numerator and denominator) and a boolean. The boolean is true if the halting condition is satisfied, and false otherwise.

In this task the parsed Fractran program is stored on the ancillary stack program.

To execute a Fractran program until the halting condition is satisfied, use [ program share run until ]. The Fractran prime generator will never satisfy the halting condition, so in this task the drop after run discards the boolean.

  [ $ "bigrat.qky" loadfile ] now! 

  [ 1 & not ]                  is even     (     n --> b     )
 
  [ nip 1 = ]                  is vint     (   n/d --> b     )
 
  [ [ dup even while
      1 >> again ]
    1 = ]                      is powerof2 (     n --> b     )
 
  [ 0 swap
    [ dup even while
      dip 1+
      1 >> again ]
    drop ]                     is lowbit   (     n --> n     )
 
  [ [] swap nest$
    witheach
      [ char / over find
        space unrot poke
        build nested join ] ]  is parse$   (     $ --> [     )
 
  [ stack ]                    is program  (     s -->       )
 
  [ true temp put
    witheach
      [ do 2over v*
        2dup vint iff
          [ false temp replace
            conclude ]
         else 2drop ]
      2swap 2drop
      temp take ]              is run      ( n/d [ --> n/d b )
 
  [ stack ]                    is primes   (       --> s     )
 
  $ "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" join
  parse$ program put
 
  2 n->v 
  15 times 
    [ program share run 
      drop over echo sp ]
  cr
  2drop
  2 n->v
  [] primes put
  [ program share run
    drop over dup powerof2 iff
      [ lowbit primes take
        swap join primes put ]
    else drop
    primes share size 20 = until ]
  2drop
  primes take echo
 
  program release

Output:

15 825 725 1925 2275 425 390 330 290 770 910 170 156 132 116
[ 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 ]

Racket

Translation of: D

Simple version, without sequences.

#lang racket

(define (displaysp x)
  (display x)
  (display " "))

(define (read-string-list str)
  (map string->number
       (string-split (string-replace str " " "") ",")))
  
(define (eval-fractran n list)
  (for/or ([e (in-list list)])
    (let ([en (* e n)])
      (and (integer? en) en))))

(define (show-fractran fr n s)
  (printf "First ~a members of fractran(~a):\n" s n)
  (displaysp n) 
  (for/fold ([n n]) ([i (in-range (- s 1))])
    (let ([new-n (eval-fractran n fr)])
      (displaysp new-n) 
      new-n))
  (void))

(define fractran
  (read-string-list 
   (string-append "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")))

(show-fractran fractran 2 15)

Output:

First 15 members of fractran(2):
2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132

Raku

(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

Red

Red ["Fractran"]

inp: ask "please enter list of fractions, or input file name: "
if exists? inpf: to-file inp [inp: read inpf]

digit: charset "0123456789"
frac: [copy p [some digit] #"/" copy q [some digit] 
		keep (as-pair to-integer p to-integer q)]
code: parse inp [collect [frac some [[some " "] frac]]]

n: to-integer ask "please enter starting number n: "
x: to-integer ask "please enter the number of terms, hit return for no limit: "
l: length? code
loop x [
	forall code [
		c: code/1
		if n % c/y = 0 [
			print n: n / c/y * c/x 
			code: head code 
			break
		]
		if l = index? code [halt]
	]
]

Output:

please enter list of fractions, or input file name: 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
please enter starting number n: 2
please enter the number of terms, hit return for no limit: 15
15
825
725
1925
2275
425
390
330
290
770
910
170
156
132
116

REXX

Programming note: extra blanks can be inserted in the fractions before and/or after the solidus [/].

showing all terms

/*REXX program runs  FRACTRAN  for a given set of  fractions  and  from a specified  N. */
numeric digits 2000                              /*be able to handle larger numbers.    */
parse arg N terms fracs                          /*obtain optional arguments from the CL*/
if     N=='' |     N==","  then     N=   2       /*Not specified?  Then use the default.*/
if terms=='' | terms==","  then terms= 100       /* "      "         "   "   "      "   */
if fracs=''                then fracs= "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'
                                                 /* [↑]  The default for the fractions. */
f= space(fracs, 0)                               /*remove all blanks from the FRACS list*/
                    do #=1  while f\=='';    parse var  f   n.#   "/"   d.#   ','   f
                    end   /*#*/                  /* [↑]  parse all the fractions in list*/
#= # - 1                                         /*the number of fractions just found.  */
say #   'fractions:'   fracs                     /*display number and actual fractions. */
say 'N  is starting at '   N                     /*display the starting number  N.      */
say terms   ' terms are being shown:'            /*display a kind of header/title.      */

    do    j=1  for  terms                        /*perform the DO loop for each   term. */
       do k=1  for  #                            /*   "     "   "   "   "    "  fraction*/
       if N // d.k \== 0  then iterate           /*Not an integer?  Then ignore it.     */
       cN= commas(N);     L= length(cN)          /*maybe insert commas into N;  get len.*/
       say right('term' commas(j), 44) "──► " right(cN, max(15, L))  /*show Nth term & N*/
       N= N  %  d.k  *  n.k                      /*calculate next term (use %≡integer ÷)*/
       leave                                     /*go start calculating the next term.  */
       end   /*k*/                               /* [↑]  if an integer, we found a new N*/
    end      /*j*/
exit 0                                           /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg ?;  do jc=length(?)-3  to 1  by -3; ?=insert(',', ?, jc); end;  return ?

output when using the default input:

14 fractions: 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
N  is starting at  2
100  terms are being shown:
                                     term 1 ──►                2
                                     term 2 ──►               15
                                     term 3 ──►              825
                                     term 4 ──►              725
                                     term 5 ──►            1,925
                                     term 6 ──►            2,275
                                     term 7 ──►              425
                                     term 8 ──►              390
                                     term 9 ──►              330
                                    term 10 ──►              290
                                    term 11 ──►              770
                                    term 12 ──►              910
                                    term 13 ──►              170
                                    term 14 ──►              156
                                    term 15 ──►              132
                                    term 16 ──►              116
                                    term 17 ──►              308
                                    term 18 ──►              364
                                    term 19 ──►               68
                                    term 20 ──►                4
                                    term 21 ──►               30
                                    term 22 ──►              225
                                    term 23 ──►           12,375
                                    term 24 ──►           10,875
                                    term 25 ──►           28,875
                                    term 26 ──►           25,375
                                    term 27 ──►           67,375
                                    term 28 ──►           79,625
                                    term 29 ──►           14,875
                                    term 30 ──►           13,650
                                    term 31 ──►            2,550
                                    term 32 ──►            2,340
                                    term 33 ──►            1,980
                                    term 34 ──►            1,740
                                    term 35 ──►            4,620
                                    term 36 ──►            4,060
                                    term 37 ──►           10,780
                                    term 38 ──►           12,740
                                    term 39 ──►            2,380
                                    term 40 ──►            2,184
                                    term 41 ──►              408
                                    term 42 ──►              152
                                    term 43 ──►               92
                                    term 44 ──►              380
                                    term 45 ──►              230
                                    term 46 ──►              950
                                    term 47 ──►              575
                                    term 48 ──►            2,375
                                    term 49 ──►            9,625
                                    term 50 ──►           11,375
                                    term 51 ──►            2,125
                                    term 52 ──►            1,950
                                    term 53 ──►            1,650
                                    term 54 ──►            1,450
                                    term 55 ──►            3,850
                                    term 56 ──►            4,550
                                    term 57 ──►              850
                                    term 58 ──►              780
                                    term 59 ──►              660
                                    term 60 ──►              580
                                    term 61 ──►            1,540
                                    term 62 ──►            1,820
                                    term 63 ──►              340
                                    term 64 ──►              312
                                    term 65 ──►              264
                                    term 66 ──►              232
                                    term 67 ──►              616
                                    term 68 ──►              728
                                    term 69 ──►              136
                                    term 70 ──►                8
                                    term 71 ──►               60
                                    term 72 ──►              450
                                    term 73 ──►            3,375
                                    term 74 ──►          185,625
                                    term 75 ──►          163,125
                                    term 76 ──►          433,125
                                    term 77 ──►          380,625
                                    term 78 ──►        1,010,625
                                    term 79 ──►          888,125
                                    term 80 ──►        2,358,125
                                    term 81 ──►        2,786,875
                                    term 82 ──►          520,625
                                    term 83 ──►          477,750
                                    term 84 ──►           89,250
                                    term 85 ──►           81,900
                                    term 86 ──►           15,300
                                    term 87 ──►           14,040
                                    term 88 ──►           11,880
                                    term 89 ──►           10,440
                                    term 90 ──►           27,720
                                    term 91 ──►           24,360
                                    term 92 ──►           64,680
                                    term 93 ──►           56,840
                                    term 94 ──►          150,920
                                    term 95 ──►          178,360
                                    term 96 ──►           33,320
                                    term 97 ──►           30,576
                                    term 98 ──►            5,712
                                    term 99 ──►            2,128
                                   term 100 ──►            1,288

showing prime numbers

Programming note: if the number of terms specified (the 2^nd argument) is negative, then only powers of two are displayed.

/*REXX program runs  FRACTRAN  for a given set of  fractions  and  from a specified  N. */
numeric digits 999;  d= digits();   w= length(d) /*be able to handle gihugeic numbers.  */
parse arg N terms fracs                          /*obtain optional arguments from the CL*/
if     N=='' |     N==","  then     N=   2       /*Not specified?  Then use the default.*/
if terms=='' | terms==","  then terms= 100       /* "      "         "   "   "      "   */
if fracs=''                then fracs= "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'
                                                 /* [↑]  The default for the fractions. */
f= space(fracs, 0)                               /*remove all blanks from the FRACS list*/
                    do #=1  while f\=='';    parse var  f    n.#   "/"   d.#   ','   f
                    end   /*#*/                  /* [↑]  parse all the fractions in list*/
#= # - 1                                         /*adjust the number of fractions found.*/
tell= terms>0                                    /*flag:  show number  or  a power of 2.*/
!.= 0;                              _= 1         /*the default value  for powers of  2. */
if \tell  then do p=1  until length(_)>d;                 _= _ + _;              !._= 1
               if p==1  then @._= left('', w + 9)        "2**"left(p, w)    ' '
                        else @._= '(prime' right(p, w)")  2**"left(p, w)    ' '
               end   /*p*/                       /* [↑]  build   powers of 2   tables.  */
L= length(N)                                     /*length in decimal digits of integer N*/
say #  'fractions:'  fracs                       /*display number and actual fractions. */
say 'N  is starting at '  N                      /*display the starting number   N.     */
if tell  then say terms  ' terms are being shown:'                     /*display header.*/
         else say 'only powers of two are being shown:'                /*   "       "   */
@a= '(max digits used:'                          /*a literal used in the   SAY   below. */

  do j=1  for  abs(terms)                        /*perform DO loop once for each  term. */
     do k=1  for  #                              /*   "     "   "    "   "    " fraction*/
     if N // d.k \== 0  then iterate             /*Not an integer?  Then ignore it.     */
     cN= commas(N);                 cj=commas(j) /*maybe insert commas into  N.         */
     if tell  then say right('term' cj, 44)   "──► "   cN      /*display Nth term and N.*/
              else if !.N  then say right('term' cj,15)  "──►"  @.N @a  right(L,w)")  " cN
     N= N  %  d.k  *  n.k                        /*calculate next term (use %≡integer ÷)*/
     L= max(L, length(N) )                       /*the maximum number of decimal digits.*/
     leave                                       /*go start calculating the next term.  */
     end   /*k*/                                 /* [↑]  if an integer, we found a new N*/
  end      /*j*/
exit 0                                           /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg ?;  do jc=length(?)-3  to 1  by -3; ?=insert(',', ?, jc); end;  return ?

output when using the input (negative fifty million) of: , -50000000

14 fractions: 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
N  is starting at  2
only powers of two are being shown:
          term 1 ──►              2**1     (max digits used:   1)   2
         term 20 ──► (prime   2)  2**2     (max digits used:   4)   4
         term 70 ──► (prime   3)  2**3     (max digits used:   5)   8
        term 281 ──► (prime   5)  2**5     (max digits used:   8)   32
        term 708 ──► (prime   7)  2**7     (max digits used:  12)   128
      term 2,364 ──► (prime  11)  2**11    (max digits used:  18)   2,048
      term 3,877 ──► (prime  13)  2**13    (max digits used:  21)   8,192
      term 8,069 ──► (prime  17)  2**17    (max digits used:  27)   131,072
     term 11,320 ──► (prime  19)  2**19    (max digits used:  30)   524,288
     term 19,202 ──► (prime  23)  2**23    (max digits used:  36)   8,388,608
     term 36,867 ──► (prime  29)  2**29    (max digits used:  46)   536,870,912
     term 45,552 ──► (prime  31)  2**31    (max digits used:  49)   2,147,483,648
     term 75,225 ──► (prime  37)  2**37    (max digits used:  58)   137,438,953,472
    term 101,113 ──► (prime  41)  2**41    (max digits used:  64)   2,199,023,255,552
    term 117,832 ──► (prime  43)  2**43    (max digits used:  67)   8,796,093,022,208
    term 152,026 ──► (prime  47)  2**47    (max digits used:  73)   140,737,488,355,328
    term 215,385 ──► (prime  53)  2**53    (max digits used:  83)   9,007,199,254,740,992
    term 293,376 ──► (prime  59)  2**59    (max digits used:  92)   576,460,752,303,423,488
    term 327,021 ──► (prime  61)  2**61    (max digits used:  95)   2,305,843,009,213,693,952
    term 428,554 ──► (prime  67)  2**67    (max digits used: 104)   147,573,952,589,676,412,928
    term 507,520 ──► (prime  71)  2**71    (max digits used: 110)   2,361,183,241,434,822,606,848
    term 555,695 ──► (prime  73)  2**73    (max digits used: 113)   9,444,732,965,739,290,427,392
    term 700,064 ──► (prime  79)  2**79    (max digits used: 123)   604,462,909,807,314,587,353,088
    term 808,332 ──► (prime  83)  2**83    (max digits used: 129)   9,671,406,556,917,033,397,649,408
    term 989,527 ──► (prime  89)  2**89    (max digits used: 138)   618,970,019,642,690,137,449,562,112
  term 1,273,491 ──► (prime  97)  2**97    (max digits used: 151)   158,456,325,028,528,675,187,087,900,672
  term 1,434,367 ──► (prime 101)  2**101   (max digits used: 157)   2,535,301,200,456,458,802,993,406,410,752
  term 1,530,214 ──► (prime 103)  2**103   (max digits used: 160)   10,141,204,801,825,835,211,973,625,643,008
  term 1,710,924 ──► (prime 107)  2**107   (max digits used: 166)   162,259,276,829,213,363,391,578,010,288,128
  term 1,818,255 ──► (prime 109)  2**109   (max digits used: 169)   649,037,107,316,853,453,566,312,041,152,512
  term 2,019,963 ──► (prime 113)  2**113   (max digits used: 175)   10,384,593,717,069,655,257,060,992,658,440,192
  term 2,833,090 ──► (prime 127)  2**127   (max digits used: 197)   170,141,183,460,469,231,731,687,303,715,884,105,728
  term 3,104,686 ──► (prime 131)  2**131   (max digits used: 203)   2,722,258,935,367,507,707,706,996,859,454,145,691,648
  term 3,546,321 ──► (prime 137)  2**137   (max digits used: 212)   174,224,571,863,520,493,293,247,799,005,065,324,265,472
  term 3,720,786 ──► (prime 139)  2**139   (max digits used: 215)   696,898,287,454,081,973,172,991,196,020,261,297,061,888
  term 4,549,719 ──► (prime 149)  2**149   (max digits used: 231)   713,623,846,352,979,940,529,142,984,724,747,568,191,373,312
  term 4,755,582 ──► (prime 151)  2**151   (max digits used: 234)   2,854,495,385,411,919,762,116,571,938,898,990,272,765,493,248
  term 5,329,875 ──► (prime 157)  2**157   (max digits used: 243)   182,687,704,666,362,864,775,460,604,089,535,377,456,991,567,872
  term 5,958,404 ──► (prime 163)  2**163   (max digits used: 252)   11,692,013,098,647,223,345,629,478,661,730,264,157,247,460,343,808
  term 6,400,898 ──► (prime 167)  2**167   (max digits used: 259)   187,072,209,578,355,573,530,071,658,587,684,226,515,959,365,500,928
  term 7,120,509 ──► (prime 173)  2**173   (max digits used: 268)   11,972,621,413,014,756,705,924,586,149,611,790,497,021,399,392,059,392
  term 7,868,448 ──► (prime 179)  2**179   (max digits used: 277)   766,247,770,432,944,429,179,173,513,575,154,591,809,369,561,091,801,088
  term 8,164,153 ──► (prime 181)  2**181   (max digits used: 280)   3,064,991,081,731,777,716,716,694,054,300,618,367,237,478,244,367,204,352
  term 9,541,986 ──► (prime 191)  2**191   (max digits used: 296)   3,138,550,867,693,340,381,917,894,711,603,833,208,051,177,722,232,017,256,448
  term 9,878,163 ──► (prime 193)  2**193   (max digits used: 299)   12,554,203,470,773,361,527,671,578,846,415,332,832,204,710,888,928,069,025,792
 term 10,494,775 ──► (prime 197)  2**197   (max digits used: 305)   200,867,255,532,373,784,442,745,261,542,645,325,315,275,374,222,849,104,412,672
 term 10,852,158 ──► (prime 199)  2**199   (max digits used: 308)   803,469,022,129,495,137,770,981,046,170,581,301,261,101,496,891,396,417,650,688
 term 12,871,594 ──► (prime 211)  2**211   (max digits used: 327)   3,291,009,114,642,412,084,309,938,365,114,701,009,965,471,731,267,159,726,697,218,048
 term 15,137,114 ──► (prime 223)  2**223   (max digits used: 345)   13,479,973,333,575,319,897,333,507,543,509,815,336,818,572,211,270,286,240,551,805,124,608
 term 15,956,646 ──► (prime 227)  2**227   (max digits used: 351)   215,679,573,337,205,118,357,336,120,696,157,045,389,097,155,380,324,579,848,828,881,993,728
 term 16,429,799 ──► (prime 229)  2**229   (max digits used: 354)   862,718,293,348,820,473,429,344,482,784,628,181,556,388,621,521,298,319,395,315,527,974,912
 term 17,293,373 ──► (prime 233)  2**233   (max digits used: 361)   13,803,492,693,581,127,574,869,511,724,554,050,904,902,217,944,340,773,110,325,048,447,598,592
 term 18,633,402 ──► (prime 239)  2**239   (max digits used: 370)   883,423,532,389,192,164,791,648,750,371,459,257,913,741,948,437,809,479,060,803,100,646,309,888
 term 19,157,411 ──► (prime 241)  2**241   (max digits used: 373)   3,533,694,129,556,768,659,166,595,001,485,837,031,654,967,793,751,237,916,243,212,402,585,239,552
 term 21,564,310 ──► (prime 251)  2**251   (max digits used: 388)   3,618,502,788,666,131,106,986,593,281,521,497,120,414,687,020,801,267,626,233,049,500,247,285,301,248
 term 23,157,731 ──► (prime 257)  2**257   (max digits used: 398)   231,584,178,474,632,390,847,141,970,017,375,815,706,539,969,331,281,128,078,915,168,015,826,259,279,872
 term 24,805,778 ──► (prime 263)  2**263   (max digits used: 407)   14,821,387,422,376,473,014,217,086,081,112,052,205,218,558,037,201,992,197,050,570,753,012,880,593,911,808
 term 26,506,125 ──► (prime 269)  2**269   (max digits used: 416)   948,568,795,032,094,272,909,893,509,191,171,341,133,987,714,380,927,500,611,236,528,192,824,358,010,355,712
 term 27,168,588 ──► (prime 271)  2**271   (max digits used: 419)   3,794,275,180,128,377,091,639,574,036,764,685,364,535,950,857,523,710,002,444,946,112,771,297,432,041,422,848
 term 28,973,145 ──► (prime 277)  2**277   (max digits used: 428)   242,833,611,528,216,133,864,932,738,352,939,863,330,300,854,881,517,440,156,476,551,217,363,035,650,651,062,272
 term 30,230,537 ──► (prime 281)  2**281   (max digits used: 435)   3,885,337,784,451,458,141,838,923,813,647,037,813,284,813,678,104,279,042,503,624,819,477,808,570,410,416,996,352
 term 30,952,920 ──► (prime 283)  2**283   (max digits used: 438)   15,541,351,137,805,832,567,355,695,254,588,151,253,139,254,712,417,116,170,014,499,277,911,234,281,641,667,985,408
 term 34,284,307 ──► (prime 293)  2**293   (max digits used: 453)   15,914,343,565,113,172,548,972,231,940,698,266,883,214,596,825,515,126,958,094,847,260,581,103,904,401,068,017,057,792
 term 39,303,996 ──► (prime 307)  2**307   (max digits used: 475)   260,740,604,970,814,219,042,361,048,116,400,404,614,587,954,389,239,840,081,425,977,517,360,806,369,707,098,391,474,864,128
 term 40,844,960 ──► (prime 311)  2**311   (max digits used: 481)   4,171,849,679,533,027,504,677,776,769,862,406,473,833,407,270,227,837,441,302,815,640,277,772,901,915,313,574,263,597,826,048
 term 41,728,501 ──► (prime 313)  2**313   (max digits used: 484)   16,687,398,718,132,110,018,711,107,079,449,625,895,333,629,080,911,349,765,211,262,561,111,091,607,661,254,297,054,391,304,192
 term 43,329,639 ──► (prime 317)  2**317   (max digits used: 490)   266,998,379,490,113,760,299,377,713,271,194,014,325,338,065,294,581,596,243,380,200,977,777,465,722,580,068,752,870,260,867,072
 term 49,260,306 ──► (prime 331)  2**331   (max digits used: 512)   4,374,501,449,566,023,848,745,004,454,235,242,730,706,338,861,786,424,872,851,541,212,819,905,998,398,751,846,447,026,354,046,107,648
...
    (some output elided.)
...
term 193,455,490 ──► (prime 523)  2**523   (max digits used: 808)   27,459,190,640,522,438,859,927,603,196,325,572,869,077,741,200,573,221,637,577,853,836,742,172,733,590,624,208,490,238,562,645,818,219,909,185,245,565,923,432,148,487,951,998,866,575,250,296,113,164,460,228,608

Output note: There are intermediary numbers (that aren't powers of two) that are hundreds of digits long.

RPL

≪ → text
  ≪ "{'" 1 text SIZE FOR j
       text j DUP SUB
       IF DUP " " == THEN DROP "' '" END +
    NEXT
    "'}" + STR→
≫ ≫ 'PRECOMPIL' STO     @ ( "fractions" → { 'fractions' } )

≪ SWAP 20 → prog steps
  ≪ {} SWAP 
     1 steps FOR n 
        1 CF
        1 prog SIZE FOR j
            prog j GET OVER * EVAL RND
            IF DUP FP THEN DROP ELSE 
               SWAP DROP SWAP OVER + SWAP
               prog SIZE 'j' STO 1 SF END
        NEXT 
        IF 1 FC?C THEN steps 'n' STO END
     NEXT DROP
≫ ≫ 'RUN20' STO         @ ( { 'fractions' } n → { results } )

"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" PRECOMPIL
2 RUN20

Output:

1: { 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132 116 308 364 68 4 30 }

Ruby

ar = %w[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]
FractalProgram = ar.map(&:to_r)                                #=> array of rationals

Runner = Enumerator.new do |y|
  num = 2
  loop{ y << num *= FractalProgram.detect{|f| (num*f).denominator == 1} }
end

prime_generator = Enumerator.new do |y| 
  Runner.each do |num|
    l = Math.log2(num)
    y << l.to_i if l.floor == l
  end
end

# demo
p Runner.take(20).map(&:numerator)
p prime_generator.take(20)

Output:

[15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4, 30]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

Scala

class TestFractran extends FunSuite {
  val program = 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")
  val expect = List(2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132)

  test("find first fifteen fractran figures") {
    assert((program .execute(2) take 15 toList) === expect)
  }
}

object Fractran {
  val pattern = """\s*(\d+)\s*/\s*(\d+)\s*""".r
  def parse(m: Match) = ((m group 1).toInt, (m group 2).toInt)
  def apply(program: String) =  new Fractran(
    pattern.findAllMatchIn(program).map(parse).toList)
}

class Fractran(val numDem: List[(Int,Int)]) {
  def execute(value: Int) = unfold(value) { v =>
    numDem indexWhere(v % _._2 == 0) match {
      case i if i > -1 => Some(v, numDem(i)._1 * v / numDem(i)._2)
      case _ => None
    }
  }
}

Scheme

Scheme naturally handles fractions, translating to integers as required. The first part of the code translates from a string representation, as required, but equally the user could type the list of fractions in directly as a list.

Library: Scheme/SRFIs

Similar to Python implementation of generating primes, the power of 2 is detected by first converting the number to binary representation, and check if it has only 1 "1" bit.

(import (scheme base)
        (scheme inexact)
        (scheme read)
        (scheme write)
        (srfi 13))   ;; for string-length and string-ref

(define *string-fractions* ; string input of fractions
  "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")

(define *fractions* ; create vector of fractions from string input
  (list->vector ; convert result to a vector, for constant access times
    (read (open-input-string ; read from the string of fractions, as a list
            (string-append "(" *string-fractions* ")")))))

;; run a fractran interpreter, returning the next number for n
;; or #f if no next number available
;; assume fractions: ordered vector of positive fractions
;;                n: a positive integer
(define (fractran fractions n)
  (let ((max-n (vector-length fractions)))
    (let loop ((i 0))
      (cond ((= i max-n)
             #f)
            ((integer? (* n (vector-ref fractions i)))
             (* n (vector-ref fractions i)))
            (else 
              (loop (+ 1 i)))))))

;; Task
(define (display-result max-n)
  (do ((i 0 (+ 1 i))
       (n 2 (fractran *fractions* n)))
    ((= i max-n) (newline))
    (display n) (display " ")))

(display "Task: ")
(display-result 20) ; show first 20 numbers

;; Extra Credit: derive first 20 prime numbers
(define (generate-primes target-number initial-n)
  (define (is-power-of-two? n) ; a binary with only 1 "1" bit is a power of 2
    (cond ((<= n 2) ; exclude 2 and 1
           #f)
          (else
            (let loop ((i 0) (acc 0) (binary-str (number->string n 2)))
              (cond ((= i (string-length binary-str))
                     #t)
                    ((and (eq? (string-ref binary-str i) #\1) (= 1 acc))
                     #f)
                    ((eq? (string-ref binary-str i) #\1)
                     (loop (+ 1 i) (+ 1 acc) binary-str))
                    (else
                      (loop (+ 1 i) acc binary-str)))))))
  (define (extract-prime n) ; just gets the number of zeroes in binary
    (let ((binary-str (number->string n 2)))
      (- (string-length binary-str) 1)))
  ;
  (let loop ((count 0)
             (n initial-n))
    (when (< count target-number)
      (cond ((eq? n #f)
             (display "-- FAILED TO COMPUTE N --\n"))
            ((is-power-of-two? n)
             (display (extract-prime n)) (display " ")
             (loop (+ 1 count)
                   (fractran *fractions* n)))
            (else
              (loop count
                    (fractran *fractions* n))))))
  (newline))

(display "Primes:\n")
(generate-primes 20 2) ; create first 20 primes

Output:

Task: 2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132 116 308 364 68 4
Primes:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71

Seed7

$ include "seed7_05.s7i";
  include "rational.s7i";

const func array integer: fractran (in integer: limit, in var integer: number, in array rational: program) is func
  result
    var array integer: output is 0 times 0;
  local
    var integer: index is 1;
    var rational: newNumber is 0/1;
  begin
    output := [] (number);
    while index <= length(program) and length(output) <= limit do
      newNumber := rat(number) * program[index];
      if newNumber = rat(trunc(newNumber)) then
        number := trunc(newNumber);
        output &:= number;
        index := 1;
      else
        incr(index);
      end if;
    end while;
  end func;

const proc: main is func
  local
    const array rational: program is []
        (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);
    var array integer: output is 0 times 0;
    var integer: number is 0;
  begin
    output := fractran(15, 2, program);
    for number range output do
      write(number <& " ");
    end for;
    writeln;
  end func;

Output:

2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132 116

Program to compute prime numbers with fractran (The program has no limit, use CTRL-C to terminate it):

$ include "seed7_05.s7i";
  include "bigrat.s7i";

const proc: fractran (in var bigInteger: number, in array bigRational: program) is func
  local
    var integer: index is 1;
    var bigRational: newNumber is 0_/1_;
  begin
    while index <= length(program) do
      newNumber := rat(number) * program[index];
      if newNumber = rat(trunc(newNumber)) then
        number := trunc(newNumber);
        if 2_ ** ord(log2(number)) = number then
          writeln(log2(number));
        end if;
        index := 1;
      else
        incr(index);
      end if;
    end while;
  end func;

const proc: main is func
  local
    const array bigRational: program is []
        (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_);
  begin
    fractran(2_, program);
  end func;

Output:

Sidef

Translation of: Ruby

var str ="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"
const FractalProgram = str.split(',').map{.num}      #=> array of rationals

func runner(n, callback) {
    var num = 2
    n.times {
        callback(num *= FractalProgram.find { |f| f * num -> is_int })
    }
}

func prime_generator(n, callback) {
    var x = 0;
    runner(Inf, { |num|
        var l = num.log2
        if (l.floor == l) {
            callback(l.int)
            ++x == n && return nil
        }
    })
}

STDOUT.autoflush(true)

runner(20, {|n| print (n, ' ') })
print "\n"

prime_generator(20, {|n| print (n, ' ') })
print "\n"

Output:

15 825 725 1925 2275 425 390 330 290 770 910 170 156 132 116 308 364 68 4 30 
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71

Tcl

Works with: Tcl version 8.6

package require Tcl 8.6

oo::class create Fractran {
    variable fracs nco
    constructor {fractions} {
	set fracs {}
	foreach frac $fractions {
	    if {[regexp {^(\d+)/(\d+),?$} $frac -> num denom]} {
		lappend fracs $num $denom
	    } else {
		return -code error "$frac is not a supported fraction"
	    }
	}
	if {![llength $fracs]} {
	    return -code error "need at least one fraction"
	}
    }

    method execute {n {steps 15}} {
	set co [coroutine [incr nco] my Generate $n]
	for {set i 0} {$i < $steps} {incr i} {
	    lappend result [$co]
	}
	catch {rename $co ""}
	return $result
    }

    method Step {n} {
	foreach {num den} $fracs {
	    if {$n % $den} continue
	    return [expr {$n * $num / $den}]
	}
	return -code break
    }
    method Generate {n} {
	yield [info coroutine]
	while 1 {
	    yield $n
	    set n [my Step $n]
	}
	return -code break
    }
}

set ft [Fractran new {
    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
}]
puts [$ft execute 2]

Output:

2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132

You can just collect powers of 2 by monkey-patching in something like this:

oo::objdefine $ft method pow2 {n} {
    set co [coroutine [incr nco] my Generate 2]
    set pows {}
    while {[llength $pows] < $n} {
	set item [$co]
	if {($item & ($item-1)) == 0} {
	    lappend pows $item
	}
    }
    return $pows
}
puts [$ft pow2 10]

Which will then produce this additional output:

2 4 8 32 128 2048 8192 131072 524288 8388608

TI-83 BASIC

Works with: TI-83 BASIC version TI-84Plus 2.55MP

100->T
2->N
{17,78,19,23,29,77,95,77, 1,11,13,15,15,55}->LA
{91,85,51,38,33,29,23,19,17,13,11,14, 2, 1}->LB
Dim(LA)->U
T->Dim(LC)
For(I,1,T)
	1->J: 1->F
	While J<=U and F=1
		If remainder(N,LB(J))=0
		Then
			Disp N 
			N->LC(I)
			iPart(N/LB(J))*LA(J)->N 
			0->F
		End
		J+1->J
	End
End

Note:

 -> stands for Store symbol
 L  stands for List  symbol in LA,LB,LC

Output:

VBA

This implementations follows the Wikipedia description of FRACTRAN. There are test, decrement and increment instructions on an array of variables which are the exponents of the prime factors of the argument, which are the only instructions used to run the program with the function run, or go through it step by step with the function steps. An auxiliary factor function is used to compile the FRACTRAN program.

Option Base 1
Public prime As Variant
Public nf As New Collection
Public df As New Collection
Const halt = 20
Private Sub init()
    prime = [{2,3,5,7,11,13,17,19,23,29,31}]
End Sub
Private Function factor(f As Long) As Variant
    Dim result(10) As Integer
    Dim i As Integer: i = 1
    Do While f > 1
        Do While f Mod prime(i) = 0
            f = f \ prime(i)
            result(i) = result(i) + 1
        Loop
        i = i + 1
    Loop
    factor = result
End Function
Private Function decrement(ByVal a As Variant, b As Variant) As Variant
    For i = LBound(a) To UBound(a)
        a(i) = a(i) - b(i)
    Next i
    decrement = a
End Function
Private Function increment(ByVal a As Variant, b As Variant) As Variant
    For i = LBound(a) To UBound(a)
        a(i) = a(i) + b(i)
    Next i
    increment = a
End Function
Private Function test(a As Variant, b As Variant)
    flag = True
    For i = LBound(a) To UBound(a)
        If a(i) < b(i) Then
            flag = False
            Exit For
        End If
    Next i
    test = flag
End Function
Private Function unfactor(x As Variant) As Long
    result = 1
    For i = LBound(x) To UBound(x)
        result = result * prime(i) ^ x(i)
    Next i
    unfactor = result
End Function
Private Sub compile(program As String)
    program = Replace(program, " ", "")
    programlist = Split(program, ",")
    For Each instruction In programlist
        parts = Split(instruction, "/")
        nf.Add factor(Val(parts(0)))
        df.Add factor(Val(parts(1)))
    Next instruction
End Sub
Private Function run(x As Long) As Variant
    n = factor(x)
    counter = 0
    Do While True
        For i = 1 To df.Count
            If test(n, df(i)) Then
                n = increment(decrement(n, df(i)), nf(i))
                Exit For
            End If
        Next i
        Debug.Print unfactor(n);
        counter = counter + 1
        If num = 31 Or counter >= halt Then Exit Do
    Loop
    Debug.Print
    run = n
End Function
Private Function steps(x As Variant) As Variant
    'expects x=factor(n)
    For i = 1 To df.Count
        If test(x, df(i)) Then
            x = increment(decrement(x, df(i)), nf(i))
            Exit For
        End If
    Next i
    steps = x
End Function
Private Function is_power_of_2(x As Variant) As Boolean
    flag = True
    For i = LBound(x) + 1 To UBound(x)
        If x(i) > 0 Then
            flag = False
            Exit For
        End If
    Next i
    is_power_of_2 = flag
End Function
Private Function filter_primes(x As Long, max As Integer) As Long
    n = factor(x)
    i = 0: iterations = 0
    Do While i < max
        If is_power_of_2(steps(n)) Then
            Debug.Print n(1);
            i = i + 1
        End If
        iterations = iterations + 1
    Loop
    Debug.Print
    filter_primes = iterations
End Function
Public Sub main()
    init
    compile ("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")
    Debug.Print "First 20 results:"
    output = run(2)
    Debug.Print "First 30 primes:"
    Debug.Print "after"; filter_primes(2, 30); "iterations."
End Sub

Output:

First 20 results:
 15  825  725  1925  2275  425  390  330  290  770  910  170  156  132  116  308  364  68  4  30 
First 30 primes:
 2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113 
after 2019962 iterations.

Wren

Translation of: Kotlin

Library: Wren-big

Extra credit is glacially slow. We just find the first 10 primes which takes about 85 seconds.

import "./big" for BigInt, BigRat

var isPowerOfTwo = Fn.new { |bi| bi & (bi - BigInt.one) == BigInt.zero }

var fractran = Fn.new { |program, n, limit, primesOnly|
    var fractions = program.split(" ").where { |s| s != "" }
                                      .map { |s| BigRat.fromRationalString(s) }
                                      .toList
    var results = []
    if (!primesOnly) results.add(n)
    var nn = BigInt.new(n)
    while (results.count < limit) {
        var fracs = fractions.where { |f| (f * nn).isInteger }.toList
        if (fracs.count == 0) break
        var frac = fracs[0]
        nn = nn * frac.num / frac.den
        if (!primesOnly) {
            results.add(nn.toSmall)
        } else if (primesOnly && isPowerOfTwo.call(nn)) {
            var prime = (nn.toNum.log / 2.log).floor
            results.add(prime)
        }
    }
    return results
}

var program = "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"
System.print("First twenty numbers:")
System.print(fractran.call(program, 2, 20, false))
System.print("\nFirst ten primes:")
System.print(fractran.call(program, 2, 10, true))

Output:

First twenty numbers:
[2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4]

First ten primes:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

zkl

var fracs="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";
fcn fractranW(n,fracsAsOneBigString){ //-->Walker (iterator)
  fracs:=(fracsAsOneBigString-" ").split(",").apply(
	 fcn(frac){ frac.split("/").apply("toInt") }); //( (n,d), (n,d), ...)
   Walker(fcn(rn,fracs){
      n:=rn.value;
      foreach a,b in (fracs){
	 if(n*a%b == 0){ 
	    rn.set(n*a/b);
	    return(n);
	 }
      }
   }.fp(Ref(n),fracs))
}

fractranW(2,fracs).walk(20).println();

Output:

L(2,15,825,725,1925,2275,425,390,330,290,770,910,170,156,132,116,308,364,68,4)

Translation of: Python

var [const] BN=Import("zklBigNum");  // libGMP
fcn fractranPrimes{
   foreach n,fr in ([1..].zip(fractranW(BN(2),fracs))){
      if(fr.num1s==1){
	 p:=(fr.toString(2) - "1").len();  // count zeros
	 if(p>1)
	    println("Prime %3d from the nth Fractran(%8d): %d".fmt(p,n,fr));
      }
   }
} 
fractranPrimes();

Output:

Prime   2 from the nth Fractran(      20): 4
Prime   3 from the nth Fractran(      70): 8
Prime   5 from the nth Fractran(     281): 32
...
Prime 227 from the nth Fractran(15956646): 215679573337205118357336120696157045389097155380324579848828881993728
Prime 229 from the nth Fractran(16429799): 862718293348820473429344482784628181556388621521298319395315527974912
Prime 233 from the nth Fractran(17293373): 13803492693581127574869511724554050904902217944340773110325048447598592
Prime 239 from the nth Fractran(18633402): 883423532389192164791648750371459257913741948437809479060803100646309888
...