Fractran language

[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 Expand

(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 Expand

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

Code Select Expand

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 Expand

(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 Expand

(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 Expand

(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 Expand

(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 Expand

(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 Expand

 (= 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 Expand

(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 Expand

(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 :-)

[rrq]

Interesting.



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

Code Select Expand

(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 Expand

(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]

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

[rrq]

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

Code Select Expand

; 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]

Thanks for another function for big integer :-)

[MariyaSn]

Arabic is my first language  Then follows English even though im better at it and now im learning French  Im not too good at it though... I want to learn French first until im fluent enough to depend on my own then probably move on to Spanish or Italian since i heard theyre similar

[iAlexpi]

Well - I think english will be a global business/tech language follwed by chinese. And then spanish/chinese/russian/english as the main languages used in the community... and a local language thrown in for home...



So yes - and no... mostly no...

[MariyaSn]

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

Your kind words warmed my heart))

[iAlexpi]

Interesting.  To gain speed, you could specialize the power-of-2 test into the following Code: Select all(nil? (find "1" (1 (bits n))))

At all I do not know, as to tell...