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