prime_game, a MATLAB code which implements John Conway's prime game program, expressed in his Fractran language. The game repeatedly alters a starting integer in such a way that all prime numbers are generated, in order. In almost every case, elements of the sequence will include very large values, requiring access to unlimited range integer arithmetic.
The Fractran program incorporates an array of rational numbers of the form m / n. The current iterate i is checked successively against each of these numbers, until ( i * m / n ) is a rational value. Then i is replaced by ( i * m / n ) and the comparison is restarted at the first rational. As the iteration proceeds, if i is returned as a power of 2, then p = log2(i) is the next prime number. If we start with n = 2, then the iteration will eventually produce the values 4=2^2, 8=2^3, 32=2^5, and so on.
The first prime numbers are rather small; however, even to compute relatively tiny prime numbers, the prime game produces a sequence of possibly great length, and of many very large numbers. In fact, the MATLAB version, while attempting to discover the prime number 7 by starting with n = 32, fails by triggering integer overflow. That is, while heading towards the output value n=128=2^7, an element of the sequence exceeds the maximum integer 2,147,483,647, causing the program to terminate early. Thus, in order to use this algorithm, a way needs to be found to compute with really large integers. program. The current version of the program has not been adapted to this need.
The information on this web page is distributed under the MIT license.
prime_game is available in a MATLAB version.