Fractran language

Q&A's, tips, howto's
Post Reply
cameyo
Posts: 115
Joined: Sun Mar 27, 2011 3:07 pm
Location: Italy

Fractran language

Post by cameyo »

Fractran is a Turing-complete esoteric programming language invented by the mathematician John Conway. A Fractran program is an ordered list of positive fractions together with an initial positive integer input n. The program is run by updating the integer n as follows:
1) For the first fraction f in the list for which n*f is an integer, replace n by n*f
2) repeat this rule until no fraction in the list produces an integer when multiplied by n, then halt.
Conway 1987 gives the following formula for primes in Fractran:

Code: Select all

(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)
Starting with n=2, this Fractran program generates the following sequence of integers:

Code: Select all

2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ...
After 2, this sequence contains the following powers of 2:

Code: Select all

2^2 = 4, 2^3 = 8, 2^5 = 32, 2^7 = 128, 2^11 = 2048
2^13 = 8192, 2^17 = 131072, 2^19 = 5244288, ...
which are the prime powers of 2.

Represent the Fractran program as a list:

Code: Select all

(setq primegame '((17L 91L) (78L 85L) (19L 51L) (23L 38L) (29L 33L)
(77L 29L) (95L 23L) (77L 19L) (1L 17L) (11L 13L) (13L 11L) (15L 14L) (15L 2L) (55L 1L) (55L 1L)))
The "fractran" function takes the program and an initial value and returns the next value or stops if no integer value is found.

Code: Select all

(define (fractran prog n)
  (local (value stop)
    (setq stop nil)
    (dolist (el prog stop)
      (setq value (/ (* (first el) n) (last el)))
      (cond ((null? prog) (setq stop true))
            ((= 0 (% (* (first el) n) (last el)))
                (setq stop true))))
    value))
Note: Since the numbers soon exceed the 64-bit integer limit we must use big-integers.
The "run" function runs the entire fractran program:

Code: Select all

(define (run program start step)
  (dotimes (x step)
    (println start)
    (setq start (fractran program start)))
  'stop)
Let's try running the fractran program:

Code: Select all

(run primegame 2L 10)
; -> 2L
; -> 15L
; -> 825L
; -> 725L
; -> 1925L
; -> 2275L
; -> 425L
; -> 390L
; -> 330L
; -> 290L
; -> stop
To extract the prime numbers it is necessary to verify if a given integer is a power of two.
We define two function "ipow" (calculate the integer power of a number) and "ilog" (calculate the integer logarithm of a number):

Code: Select all

(define (ipow x n)
  (cond ((zero? n) 1)
        ((even? n) (ipow (* x x) (/ n 2)))
        (true (* x (ipow (* x x) (/ (- n 1) 2))))))

(define (ilog n b)
  (if (zero? n) -1
    (+ (ilog (/ n b) b) 1L)))
A number n is the power of two if it is:

Code: Select all

  (= n (ipow 2 (ilog n 2)))
(= 1122 (ipow 2 (ilog 1122 2)))
; -> nil
(= 4096 (ipow 2 (ilog 4096 2)))
; -> true
Now write the "run2" function which ends the prime numbers:

Code: Select all

(define (run2 program start step)
  (dotimes (x step)
    (if (= start (ipow 2 (ilog start 2)))
      (print (ilog start 2) {, }))
    (setq start (fractran program start)))
  'stop)
Run the program to generate the prime numbers:

Code: Select all

(run2 primegame 2L 1e6)
; -> 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, stop
Conway is a very 'bad' guy :-)

ralph.ronnquist
Posts: 216
Joined: Mon Jun 02, 2014 1:40 am
Location: Melbourne, Australia

Re: Fractran language

Post by ralph.ronnquist »

Interesting.

To gain speed, you could specialize the power-of-2 test into the following

Code: Select all

(nil? (find "1" (1 (bits n))))
That method is 1-2 magnitudes faster than "proper math's", and using bits for ilog2 as well, it could become the following, faster run function:

Code: Select all

(define (run2 program start step)
  (dotimes (x step)
    (let (b (bits x)) 
       (or (find "1" (1 b)) (print (dec (length b)) ", ")))
    (setq start (fractran program start)))
  'stop)
:)

cameyo
Posts: 115
Joined: Sun Mar 27, 2011 3:07 pm
Location: Italy

Re: Fractran language

Post by cameyo »

Hi ralph.ronnquist,
i have some problems with your function.
I think that the bits function don't work with big integer.

Have a nice day

ralph.ronnquist
Posts: 216
Joined: Mon Jun 02, 2014 1:40 am
Location: Melbourne, Australia

Re: Fractran language

Post by ralph.ronnquist »

Ah. I didn't think about that. One might make a bitsL function for that, eg:

Code: Select all

; Compute "bits" for bigint and int
(constant 'MAXINT (pow 2 62))                                                    
(define (prep s) (string (dup "0" (- 62 (length s))) s))
(define (bitsL n)
    (if (<= n MAXINT) (bits (int n))
      (string (bitsL (/ n MAXINT))
              (prep (bits (int (% n MAXINT)))))))
but then I'm less sure about the gain in speed.

cameyo
Posts: 115
Joined: Sun Mar 27, 2011 3:07 pm
Location: Italy

Re: Fractran language

Post by cameyo »

Thanks for another function for big integer :-)

Post Reply