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