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

A FRACTRAN program is an ordered list of positive fractions 



P
=
(

f

1


,

f

2


,
…
,

f

m


)


{\displaystyle P=(f_{1},f_{2},\ldots ,f_{m})}

, together with an initial positive integer input 



n


{\displaystyle n}

.



The program is run by updating the integer 



n


{\displaystyle n}

 as follows:

 for the first fraction, 




f

i




{\displaystyle f_{i}}

, in the list for which 



n

f

i




{\displaystyle nf_{i}}

 is an integer, replace 



n


{\displaystyle n}

 with 



n

f

i




{\displaystyle nf_{i}}

 ;
 repeat this rule until no fraction in the list produces an integer when multiplied by 



n


{\displaystyle n}

, then halt.


Conway gave a program for primes in FRACTRAN:

 



17

/

91


{\displaystyle 17/91}

, 



78

/

85


{\displaystyle 78/85}

, 



19

/

51


{\displaystyle 19/51}

, 



23

/

38


{\displaystyle 23/38}

, 



29

/

33


{\displaystyle 29/33}

, 



77

/

29


{\displaystyle 77/29}

, 



95

/

23


{\displaystyle 95/23}

, 



77

/

19


{\displaystyle 77/19}

, 



1

/

17


{\displaystyle 1/17}

, 



11

/

13


{\displaystyle 11/13}

, 



13

/

11


{\displaystyle 13/11}

, 



15

/

14


{\displaystyle 15/14}

, 



15

/

2


{\displaystyle 15/2}

, 



55

/

1


{\displaystyle 55/1}


Starting with 



n
=
2


{\displaystyle n=2}

, this FRACTRAN program will change 



n


{\displaystyle n}

 to 



15
=
2
×
(
15

/

2
)


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

, then 



825
=
15
×
(
55

/

1
)


{\displaystyle 825=15\times (55/1)}

, generating the following sequence of integers:

 



2


{\displaystyle 2}

, 



15


{\displaystyle 15}

, 



825


{\displaystyle 825}

, 



725


{\displaystyle 725}

, 



1925


{\displaystyle 1925}

, 



2275


{\displaystyle 2275}

, 



425


{\displaystyle 425}

, 



390


{\displaystyle 390}

, 



330


{\displaystyle 330}

, 



290


{\displaystyle 290}

, 



770


{\displaystyle 770}

, 



…


{\displaystyle \ldots }


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






2

2


=
4


{\displaystyle 2^{2}=4}

, 




2

3


=
8


{\displaystyle 2^{3}=8}

, 




2

5


=
32


{\displaystyle 2^{5}=32}

, 




2

7


=
128


{\displaystyle 2^{7}=128}

, 




2

11


=
2048


{\displaystyle 2^{11}=2048}

, 




2

13


=
8192


{\displaystyle 2^{13}=8192}

, 




2

17


=
131072


{\displaystyle 2^{17}=131072}

, 




2

19


=
524288


{\displaystyle 2^{19}=524288}

, 



…


{\displaystyle \ldots }


which are the prime powers of 2.



Task

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



Extra credit

Use this program to derive the first 20 or so prime numbers.



See also

For more on how to program FRACTRAN as a universal programming language, see:

 J. H. Conway (1987). Fractran: A Simple Universal Programming Language for Arithmetic. In: Open Problems in Communication and Computation, pages 4–26. Springer.
 J. H. Conway (2010). "FRACTRAN: A simple universal programming language for arithmetic". In Jeffrey C. Lagarias. The Ultimate Challenge: the 3x+1 problem. American Mathematical Society. pp. 249–264. ISBN 978-0-8218-4940-8. Zbl 1216.68068.
 Number Pathology: Fractran by Mark C. Chu-Carroll; October 27, 2006.


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