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