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

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.

About these ads

Pages: 1 2

7 Responses to “Fractran”

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

  2. 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 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))
    
  5. madscifi said

    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;
    }
    
  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)
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 643 other followers

%d bloggers like this: