## Fractran

### July 6, 2012

The British mathematician John Horton Conway, famous for inventing the cellular automata Game of Life, also invented an esoteric programming language called fractran in which commands are represented as fractions; for instance, the primegame program generates prime numbers:

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 has two rules:

1. Find the first fraction *f* in the list for which *nf* is an integer, output *nf*, and set *n* ← *nf*.

2. Repeat the first rule, but halt if no product *nf* is integral.

For example, given an initial 2, the sequence of values produced by the above program begins 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4, …. (A007542).

The program is called primegame because the exponents of each number in the sequence that is a power of 2 form the list of prime numbers. For instance, the number 4 in the sequence is 2^{2}, for which the exponent 2 is the first prime. Fifty steps later the sequence takes the value 8 = 2^{3}. After another 211 steps the sequence takes the value 32 = 2^{5}. And so on, generating all of the prime numbers in sequence.

Your task is to write a fractran interpreter and use it to generate prime numbers using primegame. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

[…] today’s Programming Praxis exercise, our goal is to write an interpreter for the esotreric programming […]

My Haskell solution (see http://bonsaicode.wordpress.com/2012/07/06/programming-praxis-fractran/ for a version with comments):

This is my attempt in baby-clojure. First time I got to use lazy-seq as well, a fun exercise!

`(defn int? [n] (= n (bigint n)))(defn fractran [n program] (let [next-n (loop [[a & b] program] (if-not a nil (if (int? (* a n)) (* a n) (recur b))))] (if next-n (lazy-seq (cons n (fractran next-n program))) [n])))(defn power-of-2 [n] (loop [n n e 0] (if (= 1 n) e (if (int? (/ n 2)) (recur (/ n 2) (inc e)) nil))))(def primegame-program (loop [[a b & r] [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 []] (if a (recur r (conj n (/ a b))) n)))(defn primegame-run [n] (let [[next-p next-n] (loop [[a & r] (fractran n primegame-program)] (if-let [p (power-of-2 a)] [p (first r)] (recur r)))] (lazy-seq (cons next-p (primegame-run next-n)))))(def primes (primegame-run 2))(println (take 8 primes))`

I’m reposting the code,

C++, using GMP for bignums.

A Python 2.7 solution:

A Clojure solution