Fractran

From Esolang

Fractran is a game/computational model/language by John Conway.

In Fractran, a program consists of a finite list of positive, rational numbers. The input to a program is a positive integer n. The list is then searched in order, for a rational number p/q such that np/q is an integer. Then n is replaced by np/q and the search is restarted from the beginning of the list. The program halts when no such number p/q can be found, and the final n becomes the output from the program.

The power of this formalism comes from viewing numbers as products of prime powers. For example, if the input is 2^x 3^y, the following list gives output 5^xy, essentially multiplying x by y:

13/21, 385/13, 1/7, 3/11, 7/2, 1/3
  or, after prime factorization,
13/(3*7), (5*7*11)/13, 1/7, 3/11, 7/2, 1/3

John Conway made the following program for producing prime numbers:

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

If you start with n=2, it will go through exactly those powers of 2 whose exponents are prime numbers.

In 1999, this was shortened by Devin Kilminster (then a Ph.D student at the University of Western Australia, now a scientist at the Meteorological Service of New Zealand) to the following:

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

When started with n=10, this produces a sequence of powers of 10 whose exponents are successive primes.

Kilminster has since shortened the above program to produce a prime program using only nine fractions:

3/11 847/45 143/6 7/3 10/91 3/7 36/325 1/2 36/5

[edit] Interpreter

   fractran =: (*{~1 i.~[@(=<.)@:*)  NB. this is a small interpreter for fractran in J
   conwayPrimer =: 17x 78x 19x 23x 29x 77x 95x 77x 1x 11x 13x 15x 15x 55x
                  % 91x 85x 51x 38x 33x 29x 23x 19x 17x 13x 11x 14x 2x 1x NB. example program
   
   conwayPrimer fractran 2
15
   conwayPrimer fractran 15
825
   conwayPrimer fractran 825
725