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

Pages: 1 2

### 7 Responses to “Fractran”

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

```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 primes
```
3. 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))`

4. 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,
&program[ sizeof( program ) / sizeof( program ) ],
[](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;
}
```
6. Mike said

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)

```
7. David said

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