An integer computer, written as a shopping list

Fourteen Fractions, One Machine

Give an integer to Conway's fourteen ordered fractions and let the first legal multiplication fire. The rare moments when everything cancels to a power of two spell the primes, while a register lens exposes the machine inside.

There is no hidden test. At each step, scan from the left. Take the first fraction whose product with the current integer is still an integer. Start at 2. Press the green control once.

The printed object

This is PRIMEGAME in Conway's printed order. Order is control flow. Green means legal now. The brighter fraction is the first legal one, so it is the one that fires.

PRIMEGAME rack

Canonical order, start 2

Starting integer

Prime certification is only active for the published rack started at 2.

Run speed: 25 steps per beat

Current integer N 2

Ready. The first legal product will be computed here.

Exact prime-exponent registers

The initial 2 = 2^1 is not an output.

step	N	first legal	N next
0	2	ready	not fired

Read the integer sideways

Each prime is a register. Multiplying by a fraction adds the numerator's prime exponents and subtracts the denominator's. A fraction is legal only when none of those registers would go below zero.

The fraction 17/91 = 17/(7 × 13), for example, can fire only when the 7-register and 13-register are occupied. It empties one of each and puts one token in the 17-register. The rack above marks that condition directly from the current factorization.

The divisor ledger

Watch only the return states of the form 2^c × 7^(k-1). Here c is the candidate and k is its largest proper divisor. The state is a pure power of two exactly when k = 1, which is exactly when c is prime.

Build through candidate 11

candidate c	step	return state	7 exponent + 1	independent divisor

Building the divisor ledger.

Build a different machine

PRIMEGAME generates prime exponents. FRACTRAN itself is more general. Assemble four counter instructions below. The bench compiles them into fractions, then executes the counter rules and the fractions separately.

Counter machine compiler

Exact integer encoding

Four labelled instructions

INC adds one, then advances. DEC subtracts one and advances when possible, otherwise it jumps. Self-jumps are omitted because this simple compilation does not preserve them.

Initial A

Initial B

Z starts at zero. It can act as a known-empty register for an unconditional jump.

state = p_PC × 17^A × 19^B × 23^Z

INC r at i: p_i+1q_r / p_i

DEC r J at i: p_i+1 / (p_iq_r), then p_J / p_i

Direct counter semantics

Factored FRACTRAN integer

States agree at step 0.

The first compiled fraction is waiting.

step	direct	decoded from integer	branch

Visible audit

The check

The page reruns the published rack from 2 when it opens. It scans fractions in order with BigInt arithmetic, detects powers of two by their bits, and tests each exponent for primality by separate trial division.

Finite replay, recomputed now

step	state	exponent	expected next	result
Computing...

Running the audit.

External anchors

Conway's 1987 Theorem 1 supplies this ordered list of 14 fractions, the initial integer 2, and the claim about the later powers of two.
The compiler formulas and one-step correspondence are reproduced from Larchey-Wendling and Forster, Section 6.2.
The offline verifier hard-codes the source list independently, then checks this page's 14 data-fraction values against it before running either machine.

Uncertainty and limits

The arithmetic shown here is exact. There is no measurement uncertainty or rounding.
The finite replay through the fifth later power does not prove an infinite theorem. Conway's published divisor-test argument supplies the general result.
PRIMEGAME is not the universal machine claim. Universality belongs to the FRACTRAN language and its general compiler.
A browser has finite memory. The completeness result assumes unbounded natural-number storage.
A run that reaches this page's 20,000-step safety cap is paused, not halted. A throttled or closed tab is also not a halt.

Free choices and vacuous settings

You may change the starting integer, fraction order, or enabled fractions. Those are free sandbox choices, and prime certification turns off because the theorem no longer applies.
The compiler's distinct PC primes 2, 3, 5, 7, 11, 13 and register primes 17, 19, 23 are free coding choices. Any mutually distinct primes work.
The four instructions and initial counters are yours. The transfer preset is only a worked example.
The counter comparison would be vacuous if it copied counter values into the fraction side. It does not. That side is decoded afresh by factoring its integer after every step.
Self-looping DEC jumps are excluded. Their compiled fraction p_i/p_i would equal 1 and capture unrelated states.

Offline check: node research/fractran/verify-fractran.mjs. It reproduces the published anchors, five power events, every branch of the transfer preset, all decoded states, and the halt after eleven matched counter steps.

Sources and record checks

Primary object. J. H. Conway, "FRACTRAN: A Simple Universal Programming Language for Arithmetic", in Open Problems in Communication and Computation, Springer, 1987. The source record identifies the title, sole author, year, and DOI. The chapter scan supplies the printed fraction order, starting value, and Theorem 1 statement.

Formal compiler. Dominique Larchey-Wendling and Yannick Forster, "Hilbert's Tenth Problem in Coq (Extended Version)", Logical Methods in Computer Science 18(1), 2022. The journal page and arXiv record 2003.04604 agree on the title and both authors. The journal page gives publication on 1 March 2022. The arXiv record lists five versions, with version 5 dated 28 February 2022.