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.

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 as follows:Conway’s PRIMEGAME takes whole numbers as inputs and outputs if and only if is prime.

- for the first fraction in the list for which is an integer, replace by ;
- 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:

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.

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.

You must be logged in to post a comment.