This site is supported by donations to The OEIS Foundation.
Conway's PRIMEGAME
Conway's PRIMEGAME is an algorithm devised by John H. Conway 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. Thus A007542 is generated. Except for the initial 2, each number in A007542 having an integer for a binary logarithm is a prime number, which is to say that powers of 2 with composite exponents (A073718) don't show up.
It may be helpful to think of the "machine" as an actual machine, with an intake on one end and an outtake on the other end. A workpiece, in this case, a power of 2, is fed into the intake, the machine is activated and after making some noise and shaking, the workpiece comes out the other end transformed into another power of 2. And of course we can take this new power of 2 and put it into the intake once again. The following illustration shows an 8 going in and a 32 coming out:
An effort was made to show or at least give an idea how many times each pathway is trod by the number of arrowheads or the thickness of the lines. (Note that the illustration above uses a slightly different version of the machine that appeared in R. K. Guy's 1983 paper).
Viewed this way, we can roughly generalize what goes on inside the machine:
- A power of 2 is taken in. Gradually, instances of 2 as a prime factor (henceforth called just "2s"), are gradually stripped out, while 3s and 5s are added in.
- Once the 2s are stripped out, this is multiplied by 55, adding another 5 and introducing an 11.
- For as long as there are 3s and 11s, these are stripped out while 7s are added in (the 11 added at each multiply by 77 twenty-ninths step is removed in the following multiply by 29 thirty-thirds step).
- Once the 3s are removed but there is an 11 left, this is "traded" for a 13.
- Thanks to all the 7s added by going through 77 twenty-ninths, the machine now goes into a cycle of removing 5s, 7s and 13s while adding 2s and 3s.
- If there is a 13 left but no more 7s, the 13 is traded for an 11.
- If there is a 3 left, then with the traded-in 11 there can be another go at the 29/33 and 77/29 loop.
- But if after the 17/91 and 78/85 loop there are is a 7s but no 13s, and a 17 but no 5s, then the 17 is divided out.
- At this point, if there are factors other than 2, such as a 7, then the 7 is divided out, while a 3, 5 and 11 is added in, permitting another go through the 29/33 and 77/29 loop.
- But if there are no factors other than 2, then the number is a power of 2 and it is output.
Not all numbers of the machine are used at each stage. In going from 8 to 32, for example, there is no need to call on 19/51, 23/38, 95/23 or 77/19.
The machine bears some resemblance to a Rube Goldberg device. It takes over seven hundred steps to obtain the first four primes, whereas the sieve of Eratosthenes in about three steps.
Here are some selected points of interest in A007542:
- At step 0, we have 2, which is multiplied by 15/2 to get...
- At step 1, we have 15.
- At step 18, we have 68, which is divided by 17 to get...
- At step 19, we have 4, giving us the first prime number, 2, as its binary logarithm.
- At step 68, we have 136, which is divided by 17 to get...
- At step 69, we have 8, giving us the second prime number, 3.
- At step 280, we have 544, which is divided by 17 to get...
- At step 281, we have 32, giving us the third prime number, 5.
- At step 709, we have 2176, which is divided by 17 to get...
- At step 710, we have 128, giving us the fourth prime number, 7.
- At step 2375, we have 2048, giving us the fifth prime number, 11.
- At step 3893, we have 8192, giving us the sixth prime number, 13.
- At step 8102, we have 131072, giving us the seventh prime number, 17.
The machine can also handle some inputs that are not powers of 2 with a prime exponent: fed 16, the machine returns 32; fed 64, the machine returns 128; etc. Nor does the input have to be a power of 2 at all: fed 3, the machine returns 2; fed 10, the machine returns 8; etc. But the following input values must be avoided so as to not get the machine stuck in an infinite loop: 1, 5, 7, 11, 13, 17, 19, 22, 25, 26, etc.
References
- J. H. Conway, "FRACTRAN: a simple universal programming language for arithmetic", in T. M. Cover and Gopinath, eds., Open Problems in Communication and Computation, Springer, NY 1987, pp. 4-26.
- R. K. Guy, "Conway's prime producing machine". Math. Mag. 56 (1983), no. 1, 26-33.
- D. Olivastro, Ancient Puzzles. Bantam Books, NY, 1993, p. 21.
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995