14 1. Elementary Prime Number Theory, I
A B C D E F G H I J K L M N
17
91
78
85
19
51
23
38
29
33
77
29
95
23
77
19
1
17
11
13
13
11
15
2
1
7
55
1
Now run the following algorithm: Beginning with the number 2, look for
the first (leftmost) fraction which can be multiplied by the current number
to give an integer. Perform the multiplication and repeat. Whenever you
reach a power of 2, output the exponent. The first several (19) steps of the
algorithm are
2 15 825 725 1925 2275 425 390 330 290 770
910 170 156 132 116 308 364 68 4 =
22,
and so the first output is 2. Fifty more steps yield
22
30 225 12375 · · · 232 616 728 136 8 =
23,
and so the second output is 3. After another 212 steps, we arrive at 32 =
25,
and so our third output is 5.
Theorem 1.8 (Conway). The sequence of outputs is exactly the sequence
of primes in increasing order.
This is rather striking; the sequence of primes, which seems random in
so many ways, is the output of a deterministic algorithm involving 14 frac-
tions. But perhaps this should not come as such a shock. Most anyone who
has experimented with programming knows that the primes are the output
of a deterministic algorithm: Test the numbers 2, 3, 4,... successively for
primality, using (say) trial division for the individual tests. And actually,
underneath the surface, this is exactly what is being done in Conway’s al-
gorithm. This sequence of 14 fractions encodes a simple computer program:
The number n is tested for divisibility first by d = n 1, then d = n 2,
etc; as soon as a divisor is found, n is incremented by 1 and the process is
repeated. The game is rigged so that a power of 2 arises only when d reaches
1, i.e., when n is prime. Moreover, there is nothing special in Theorem 1.8
about the sequence of primes; an analogue of Theorem 1.8 can be proved
for any recursive set. (Here a set of natural numbers S is called recursive
if there is an algorithm for determining whether a natural number belongs
to S.) We conclude that while Conway’s result is genuinely surprising, the
surprise is that one can simulate computer programs with lists of fractions,
and is in no way specific to the prime numbers.
8. Euler’s prime-producing polynomial
The prime-producing functions we have been considering up to now have all
been rather complicated. In some sense this is necessary; one can show that
Previous Page Next Page