# John Conway's FRACTRAN in Racket

**URL:** <https://racket.discourse.group/t/john-conways-fractran-in-racket/3768>\
**Category:** Show & Tell\
**Tags:** math\
**Created:** [June 2, 2025, 12:20pm UTC](https://racket.discourse.group/t/john-conways-fractran-in-racket/3768 "2025-06-02T12:20:28Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![shawnw](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/shawnw/32/1031_2.png) [@shawnw](https://racket.discourse.group/u/shawnw)\
**Post date:** [June 2, 2025, 12:20pm UTC](https://racket.discourse.group/t/john-conways-fractran-in-racket/3768/1 "2025-06-02T12:20:28Z")

</div>

Recently in a Hacker News post, I learned about the existence of Conway's [FRACTRAN](https://en.wikipedia.org/wiki/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](https://oeis.org/A007542) are not themselves prime, and only some of them represent the primes.

Anyways, the toy I came up with:

```scheme
#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)

```