FRACTRAN is a Turing-complete esoteric programming language invented by the mathematician John Horton Conway.

A FRACTRAN program is an ordered list of positive fractions 



P
=
(

f

1


,

f

2


,
…
,

f

m


)


{\displaystyle P=(f_{1},f_{2},\ldots ,f_{m})}

, together with an initial positive integer input 



n


{\displaystyle n}

.



The program is run by updating the integer 



n


{\displaystyle n}

 as follows:

 for the first fraction, 




f

i




{\displaystyle f_{i}}

, in the list for which 



n

f

i




{\displaystyle nf_{i}}

 is an integer, replace 



n


{\displaystyle n}

 with 



n

f

i




{\displaystyle nf_{i}}

 ;
 repeat this rule until no fraction in the list produces an integer when multiplied by 



n


{\displaystyle n}

, then halt.


Conway gave a program for primes in FRACTRAN:

 



17

/

91


{\displaystyle 17/91}

, 



78

/

85


{\displaystyle 78/85}

, 



19

/

51


{\displaystyle 19/51}

, 



23

/

38


{\displaystyle 23/38}

, 



29

/

33


{\displaystyle 29/33}

, 



77

/

29


{\displaystyle 77/29}

, 



95

/

23


{\displaystyle 95/23}

, 



77

/

19


{\displaystyle 77/19}

, 



1

/

17


{\displaystyle 1/17}

, 



11

/

13


{\displaystyle 11/13}

, 



13

/

11


{\displaystyle 13/11}

, 



15

/

14


{\displaystyle 15/14}

, 



15

/

2


{\displaystyle 15/2}

, 



55

/

1


{\displaystyle 55/1}


Starting with 



n
=
2


{\displaystyle n=2}

, this FRACTRAN program will change 



n


{\displaystyle n}

 to 



15
=
2
×
(
15

/

2
)


{\displaystyle 15=2\times (15/2)}

, then 



825
=
15
×
(
55

/

1
)


{\displaystyle 825=15\times (55/1)}

, generating the following sequence of integers:

 



2


{\displaystyle 2}

, 



15


{\displaystyle 15}

, 



825


{\displaystyle 825}

, 



725


{\displaystyle 725}

, 



1925


{\displaystyle 1925}

, 



2275


{\displaystyle 2275}

, 



425


{\displaystyle 425}

, 



390


{\displaystyle 390}

, 



330


{\displaystyle 330}

, 



290


{\displaystyle 290}

, 



770


{\displaystyle 770}

, 



…


{\displaystyle \ldots }


After 2, this sequence contains the following powers of 2:






2

2


=
4


{\displaystyle 2^{2}=4}

, 




2

3


=
8


{\displaystyle 2^{3}=8}

, 




2

5


=
32


{\displaystyle 2^{5}=32}

, 




2

7


=
128


{\displaystyle 2^{7}=128}

, 




2

11


=
2048


{\displaystyle 2^{11}=2048}

, 




2

13


=
8192


{\displaystyle 2^{13}=8192}

, 




2

17


=
131072


{\displaystyle 2^{17}=131072}

, 




2

19


=
524288


{\displaystyle 2^{19}=524288}

, 



…


{\displaystyle \ldots }


which are the prime powers of 2.



Task

Write a program that reads a list of fractions in a natural format from the keyboard or from a string,
to parse it into a sequence of fractions (i.e. two integers),
and runs the FRACTRAN starting from a provided integer, writing the result at each step.
It is also required that the number of steps is limited (by a parameter easy to find).



Extra credit

Use this program to derive the first 20 or so prime numbers.



See also

For more on how to program FRACTRAN as a universal programming language, see:

 J. H. Conway (1987). Fractran: A Simple Universal Programming Language for Arithmetic. In: Open Problems in Communication and Computation, pages 4–26. Springer.
 J. H. Conway (2010). "FRACTRAN: A simple universal programming language for arithmetic". In Jeffrey C. Lagarias. The Ultimate Challenge: the 3x+1 problem. American Mathematical Society. pp. 249–264. ISBN 978-0-8218-4940-8. Zbl 1216.68068.
 Number Pathology: Fractran by Mark C. Chu-Carroll; October 27, 2006.


(import (scheme base)
        (scheme inexact)
        (scheme read)
        (scheme write)
        (srfi 13))   ;; for string-length and string-ref
 
(define *string-fractions* ; string input of fractions
  "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")
 
(define *fractions* ; create vector of fractions from string input
  (list->vector ; convert result to a vector, for constant access times
    (read (open-input-string ; read from the string of fractions, as a list
            (string-append "(" *string-fractions* ")")))))
 
;; run a fractran interpreter, returning the next number for n
;; or #f if no next number available
;; assume fractions: ordered vector of positive fractions
;;                n: a positive integer
(define (fractran fractions n)
  (let ((max-n (vector-length fractions)))
    (let loop ((i 0))
      (cond ((= i max-n)
             #f)
            ((integer? (* n (vector-ref fractions i)))
             (* n (vector-ref fractions i)))
            (else 
              (loop (+ 1 i)))))))
 
;; Task
(define (display-result max-n)
  (do ((i 0 (+ 1 i))
       (n 2 (fractran *fractions* n)))
    ((= i max-n) (newline))
    (display n) (display " ")))
 
(display "Task: ")
(display-result 20) ; show first 20 numbers
 
;; Extra Credit: derive first 20 prime numbers
(define (generate-primes target-number initial-n)
  (define (is-power-of-two? n) ; a binary with only 1 "1" bit is a power of 2
    (cond ((<= n 2) ; exclude 2 and 1
           #f)
          (else
            (let loop ((i 0) (acc 0) (binary-str (number->string n 2)))
              (cond ((= i (string-length binary-str))
                     #t)
                    ((and (eq? (string-ref binary-str i) #\1) (= 1 acc))
                     #f)
                    ((eq? (string-ref binary-str i) #\1)
                     (loop (+ 1 i) (+ 1 acc) binary-str))
                    (else
                      (loop (+ 1 i) acc binary-str)))))))
  (define (extract-prime n) ; just gets the number of zeroes in binary
    (let ((binary-str (number->string n 2)))
      (- (string-length binary-str) 1)))
  ;
  (let loop ((count 0)
             (n initial-n))
    (when (< count target-number)
      (cond ((eq? n #f)
             (display "-- FAILED TO COMPUTE N --\n"))
            ((is-power-of-two? n)
             (display (extract-prime n)) (display " ")
             (loop (+ 1 count)
                   (fractran *fractions* n)))
            (else
              (loop count
                    (fractran *fractions* n))))))
  (newline))
 
(display "Primes:\n")
(generate-primes 20 2) ; create first 20 primes