## Fractran

### July 6, 2012

We save the program in a list:

`(define 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))

The fractran interpreter takes a program and an initial value and returns the next value in the sequence, stopping if no next value can be found:

`(define (fractran prog n)`

(let loop ((fs prog))

(cond ((null? fs) 'halt)

((integer? (* (car fs) n))

(* (car fs) n))

(else (loop (cdr fs))))))

For example, here are the first twenty terms of the primegame sequence:

`> (let loop ((n 2) (k 20))`

(when (positive? k)

(display n) (display " ")

(loop (fractran primegame n) (- k 1))))

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

We generate prime numbers by looping through the primegame sequence looking for powers of 2:

`(define (primes)`

(let loop ((k 1) (n 2))

(when (= (expt 2 (ilog 2 n)) n)

(display k) (display " ")

(display (ilog 2 n)) (newline))

(loop (+ k 1) (fractran primegame n))))

Here’s the list. Notice how the distance between successive primes grows:

`> (primes)`

1 1

20 2

70 3

281 5

708 7

2364 11

3877 13

8069 17

11320 19

19202 23

36867 29

45552 31

75225 37

101113 41

117832 43

152026 47

215385 53

293376 59

327021 61

428554 67

507520 71

555695 73

700064 79

808332 83

989527 89

1273491 97

^C

We used ilog from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/cm4wvLt8. This exercise was inspired by an exercise at Reddit.

[…] 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