Tag Archives: john conway

Apr7

Conway’s Prime Producing Machine

Posted on by
Standard

Primes are not randomly arranged (since their position is predetermined) but we can’t find an equation which directly gives us nth prime number. However, we can ask for a function (which surely can’t be a polynomial) which will give only the prime numbers as output. For example, the following one is used for MRDP theorem:

 

But it’s useless to use this to find bigger primes because the computations are much more difficult than the primality tests.

Conway’s PRIMEGAME takes whole numbers as inputs and outputs 2^k if and only if k is prime.

6ZPkF

Source: https://cstheory.stackexchange.com/a/14727 [Richard Guy, © 1983 Mathematical Association of America]

 PRIMEGAME is based on a Turing-complete esoteric programming language called FRACTRAN, invented by John Conway. A FRACTRAN program is an ordered list of positive fractions together with an initial positive integer input n. The program is run by updating the integer n as follows:

  1. for the first fraction f in the list for which nf is an integer, replace n by nf;
  2. repeat this rule until no fraction in the list produces an integer when multiplied by n, then halt.

PRIMEGAME is an algorithm devised to generate primes using a sequence of 14 rational numbers:

\displaystyle{\left( \frac{17}{91}, \frac{78}{85}, \frac{19}{51}, \frac{23}{38}, \frac{29}{33}, \frac{77}{29}, \frac{95}{23}, \frac{77}{19}, \frac{1}{17}, \frac{11}{13}, \frac{13}{11}, \frac{15}{2}, \frac{1}{7}, \frac{55}{1} \right)}

Starting with 2, one finds the first number in the machine that multiplied by 2 gives an integer; then for that integer we find the first number in the machine that generates another integer. Except for the initial 2, each number output have an integer for a binary logarithm is a prime number, which is to say that powers of 2 with composite exponents don’t show up.

If you have some knowledge of computability and unsolvability theory, you can try to understand the working of this Turing machine. There is a nice exposition on OeisWiki  to begin with.

green

“Hilbert’s 10th Problem” by Martin Davis and Reuben Hersh [© 1973 Scientific American, doi: 10.1038/scientificamerican1173-84] Illustrating the basic idea of machines from unsoilvability theory.

Following is an online program by Prof. Andrew Granville illustrating the working of PRIMEGAME:

Motivation for this post came from Andrew Granville’s Math Mornings at Yale.