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 22, for which the exponent 2 is the first prime. Fifty steps later the sequence takes the value 8 = 23. After another 211 steps the sequence takes the value 32 = 25. 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.
Programming Praxis 
[…] 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):
import Data.List fractran :: [(Integer, Integer)] -> Integer -> [Integer] fractran xs = unfoldr (\m -> fmap ((,) m) . lookup 0 $ map (\(n,d) -> (mod (m*n) d, div (m*n) d)) xs) primegame :: [(Integer, Integer)] primegame = zip [17,78,19,23,29,77,95,77, 1,11,13,15,15,55] [91,85,51,38,33,29,23,19,17,13,11,14, 2, 1] primes :: [(Integer, Integer)] primes = [(i,e) | (i,n) <- zip [1..] $ fractran primegame 2 , let e = round $ log (fromIntegral n) / log 2, 2^e == n] main :: IO () main = mapM_ print $ take 26 primesThis 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,
(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))C++, using GMP for bignums.
#include <iostream> #include <gmpxx.h> template<class T> mpz_class Fractran( mpz_class n, const int* p, const int* pend, T printer ) { const int* cp = p; while( cp != pend ) { if( ( n * *cp ) % *(cp+1) == 0 ) { n = ( n * *cp ) / *(cp+1); cp = p; printer( n ); } else { cp += 2; } } return n; } int main( int argc, char *arg[] ) { int 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 }; Fractran( 2, &program[0], &program[ sizeof( program ) / sizeof( program[0] ) ], [](const mpz_class& n) { mpz_class r; int e = mpz_remove( r.get_mpz_t(), n.get_mpz_t(), mpz_class(2).get_mpz_t() ); if( r == 1 ) { std::cout << e << " " << n << std::endl; if( e > 100 ) exit(0); } } ); return 0; }A Python 2.7 solution:
def fractran(prog, n): while True: n = next(n*num/den for num,den in prog if not n*num%den) yield n def primes(): ''' a generator of prime numbers. >>> from itertools import islice >>> list(islice(primes(), 20)) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71] ''' from math import log 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)] for n in fractran(primegame, 2): e = round(log(n, 2)) if pow(2, e) == n: yield int(e)A Clojure solution
(def 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]) (defn fractran-step "Perform one Fractran step" [n] (loop [l primegame] (if (nil? l) nil (let [nf (* (first l) n)] (if (integer? nf) nf (recur (rest l))))))) (defn fractran "Return lazy fractran sequence" [n] (take-while #(not (nil? %1)) (iterate fractran-step n))) (defn factor-2s "return argument N as vector [s,d] where N = (2^S)*d" [n] (loop [n' n, e 0] (if (even? n') (recur (/ n' 2) (inc e)) [e n']))) (defn primes [] (map first (filter #(= (second %1) 1) (map factor-2s (fractran 2))))) user=> (take 20 (primes)) (1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67)