Fractran language
Posted: Mon Nov 18, 2019 3:51 pm
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:
Starting with n=2, this Fractran program generates the following sequence of integers:
After 2, this sequence contains the following powers of 2:
which are the prime powers of 2.
Represent the Fractran program as a list:
The "fractran" function takes the program and an initial value and returns the next value or stops if no integer value is found.
Note: Since the numbers soon exceed the 64-bit integer limit we must use big-integers.
The "run" function runs the entire fractran program:
Let's try running the fractran program:
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):
A number n is the power of two if it is:
Now write the "run2" function which ends the prime numbers:
Run the program to generate the prime numbers:
Conway is a very 'bad' guy :-)
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)
Code: Select all
2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ...
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, ...
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)))
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))
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)
Code: Select all
(run primegame 2L 10)
; -> 2L
; -> 15L
; -> 825L
; -> 725L
; -> 1925L
; -> 2275L
; -> 425L
; -> 390L
; -> 330L
; -> 290L
; -> stop
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)))
Code: Select all
(= n (ipow 2 (ilog n 2)))
(= 1122 (ipow 2 (ilog 1122 2)))
; -> nil
(= 4096 (ipow 2 (ilog 4096 2)))
; -> true
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)
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