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.Prof. Andrew Granville illustrating the working of PRIMEGAME:
Motivation for this post came from Andrew Granville’s Math Mornings at Yale.