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 q1, q2,...,qk. You start with some integer x0 and each subsequent xi+1 is given by xi+1=qjxi, where qj is the first number in the sequence such that qjxi 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 x0=2, and any power of 2 that occurs in the computation is 2p 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 x0=10 and shows primes as powers of ten.

Log in or register to write something here or to contact authors.