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.

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 613 other followers

%d bloggers like this: