Elegant Addition-only Prime Generation in LISP

Brief history of LISP. LISP is a functional programming language that was created in the late 1950s by John McCarthy at MIT. It quickly became the lingua franca for symbolic AI because of its tiny, expressive core: homoiconic syntax (code-as-data), first-class functions/closures, macros that extend the language, and automatic memory management. McCarthy emphasized writing programs that mirror the ideas they express; Gregory Chaitin’s work in algorithmic information theory echoes this with the pursuit of minimal descriptions—short programs that capture a concept cleanly. This post aims to do just that: a compact, clear program for primes using only additions of one (increments) and comparison as arithmetic operations.

The “Prime Clockwork” idea

Imagine every prime number p has a tiny clock – represented as an element in a LISP list – that ticks by +1 each step and resets to 0 after p steps. At “time” n, a clock reads n mod p. A number n is composite iff there exists a prime p with ${p \mid n}$ , i.e., the p-clock shows 0 at time n. So, if no clock shows 0, n is prime, and we add a new clock for p = n. This realizes divisibility using only addition: repeatedly increment a hand and wrap it to zero on overflow.

The Program (addition-only)

(let ((cs nil) (n 2))    ; cs = list of clocks (p . s), n = candidate
  (labels
      ((composite-p ()
         (some (lambda (c) (zerop (cdr c))) cs))
       (tick ()
         (dolist (c cs)
           (incf (cdr c))
           (when (= (cdr c) (car c)) (setf (cdr c) 0)))))
    (loop
      (if (composite-p)
          (progn (tick) (incf n))          ; composite → advance
          (progn (print n)                 ; prime → print & add its clock
                 (push (cons n 0) cs)
                 (tick) (incf n))))))

Beginner’s Walkthrough

State: Inside let we keep:

cs — a list of clocks; each clock is a cons pair (p . s) where p is the period (prime) and s is the current hand (from 0 to p-1).
n — the current candidate integer, starting at 2.

Local helpers with labels:

(composite-p) returns true if any clock shows 0: (some (lambda (c) (zerop (cdr c))) cs). Here, (car c) is the period; (cdr c) is the hand.
(tick) advances every clock by +1 via (incf (cdr c)) and wraps to 0 when the hand equals its period: (when (= (cdr c) (car c)) (setf (cdr c) 0)). This is our addition-only “modulus.”

Main loop:

If (composite-p) is true, n is composite → just (tick) and (incf n).
If not composite, n is prime → (print n), add a clock (n . 0) with push, then (tick) and (incf n).

Why this is addition-only: Divisibility by a prime p is detected because the p-clock’s hand cycles through ${\{0,1,\dots,p-1\}}$ by repeated addition, hitting ${0}$ exactly on multiples of ${p}$ . No ${\times}$ , ${\div}$ , or ${\bmod}$ are used—only increments and equality tests.

Why LISP helps here

Uniform, small core: cons pairs ((p . s)) model clocks directly.
Local abstractions: labels keeps tiny helpers close to their state for clarity.
Expressive control: loop, dolist, some, incf, and setf map the concept to code with minimal code.

In McCarthy’s spirit, the program mirrors its idea; in Chaitin’s spirit, it’s a short, transparent description of prime detection via periodic behavior.

Example run

Evaluating the program prints primes indefinitely (one per line). The start of an example run:

Note: Since it runs forever, stop it with your Lisp environment’s interrupt (often Ctrl-C).

References & links

McCarthy, J. (1960). Recursive functions of symbolic expressions and their computation by machine, part I. Communications of the ACM, 3(4), 184-195.
Shasha, D. and Lazere, C. (1998). Out of their minds: The lives and discoveries of 15 great computer scientists. Copernicus (NY).
Chaitin, G. J. (1977). Algorithmic information theory. IBM journal of research and development, 21(4), 350-359.
Michael T. M. Emmerich, “Prime Clockwork,” emmerix.net.

Cite this post

Please cite as:

Michael Emmerich (2025, October 26). Elegant Addition-only Prime Generation in LISP. Mathematical Playground.