A game invented by John Conway. Or a programming language, if you prefer.

A fractran program/game/instance is given as a list of rational numbers *q*_{1}, q_{2},...,q_{k}. You start with some integer *x*_{0} and each subsequent *x*_{i+1} is given by *x*_{i+1}=q_{j}x_{i}, where *q*_{j} is the first number in the sequence such that *q*_{j}x_{i} is an integer. Computation proceeds until no such number can be found in the sequence.

It's a very simple model of computation, in the sense of having very few instructions, and rather surprisingly it can be shown that fractran can compute any computable function.

The classic (only?) example of a fractran program is

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

which can compute prime numbers: you start with *x*_{0}=2, and any power of 2 that occurs in the computation is 2^{p} where p is a prime number.

I've found in a web page (http://www.maths.uwa.edu.au/seminars/1999/Pure/13.html) another, shorter, prime-calculating program:

7/3 99/98 13/49 39/35 36/91 10/143 49/13 7/11 1/2 91/1

which uses *x*_{0}=10 and shows primes as powers of ten.