Problem Statement

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:

Conway gave a program for primes in FRACTRAN: 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: After 2, this sequence contains the following powers of 2: which are the prime powers of 2.

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

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

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

Let's start with the solution:

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))