John Conway's FRACTRAN in Racket

Show & Tell
1

Recently in a Hacker News post, I learned about the existence of Conway's FRACTRAN, an esoteric programming language based on multiplying integers with rational numbers until the result is an integer (Then repeat). One of his example programs is a prime number generator, PRIMEGAME. The language itself is extremely simple and lends itself well to a recursive interpreter. Decoding the output of the PRIMEGAME program was the hard part, as the numbers it generates are not themselves prime, and only some of them represent the primes.

Anyways, the toy I came up with:

#lang racket/base

(require racket/fixnum racket/stream soup-lib/stream)

;;; The interpreter.
;;; programs can potentially never halt, so return output in a lazy stream
(define (fractran n prog)
  (define nf (for/first ([f (in-list prog)]
                         #:do [(define nf (* n f))]
                         #:when (integer? nf))
               nf))
  (if nf
      (stream-cons #:eager nf (fractran nf prog))
      empty-stream))

;;;; PRIMEGAME

(define (power-of-two? n)
  ;; Positive integers only
  (if (fixnum? n)
      (= (fxpopcount n) 1)
      (zero? (bitwise-xor n (arithmetic-shift 1 (bitwise-first-bit-set n))))))

;;; If a number can be represented as 2^N where N is an integer, return N, otherwise #f
(define (integer-exponent n)
  (if (power-of-two? n)
      (bitwise-first-bit-set n)
      #f))

;;; Return the first `count` primes.
(define (primes count)
  (define primegame '(17/91 78/85 19/51 23/38 29/33 77/29 95/23 77/19 1/17 11/13 13/11 15/2 1/7 55))
  (stream->list (stream-take (stream-filter-map integer-exponent (fractran 2 primegame)) count)))

(println (primes 10)) ; '(2 3 5 7 11 13 17 19 23 29)
4 Likes