16-1 Introduction

Like many young students, I once became fascinated with prime numbers, and tried to find a formula for them. I didn't know exactly what operations would be considered valid in a "formula," or exactly what function I was looking for梐 formula for the nth prime in terms of n, or in terms of the previous prime(s), or a formula that produces primes but not all of them, and so on. Nevertheless, in spite of these ambiguities, I would like to discuss a little of what is known about this problem. We will see that (a) there are formulas for primes, and (b) none of them are very satisfying.

Much of this subject relates to the present work in that it deals with formulas similar to those of some of our programming tricks, albeit in the domain of real number arithmetic rather than "computer arithmetic." But let us first review a few highlights from the history of this subject.

In 1640, Fermat conjectured that the formula

graphics/16icon01.gif

 

always produces a prime, and numbers of this form have come to be called "Fermat numbers." It is true that Fn is prime for n ranging from 0 to 4, but Euler found in 1732 that

graphics/16icon02.gif

 

(We have seen these factors before in connection with dividing by a constant on a 32-bit machine). Then, F. Landry showed in 1880 that

graphics/16icon03.gif

 

Fn is now known to be composite for many larger values of n, such as all n from 7 to 16 inclusive. For no value of n > 4 is it known to be prime [H&W]. So much for rash conjectures. [1]

[1] However, this is the only conjecture of Fermat known to be wrong [Wells].

Incidentally, why would Fermat be led to the double exponential? He knew that if m has an odd factor other than 1, then 2m + 1 is composite. For if m = ab with b odd and not equal to 1, then

graphics/16icon04.gif

 

Knowing this, he must have wondered about 2m + 1 with m not containing any odd factors (other than 1)梩hat is, m = 2n. He tried a few values of n and found that graphics/16icon05.gifseemed to be prime.

Certainly everyone would agree that a polynomial qualifies as a "formula." One rather amazing polynomial was discovered by Leonhard Euler in 1772. He found that

graphics/16icon06.gif

 

is prime-valued for every n from 0 to 39. His result can be extended. Because

graphics/16icon07.gif

 

f(-n) is prime-valued for every n from 1 to 40; that is, f(n) is prime-valued for every n from -1 to -40. Therefore,

graphics/16icon08.gif

 

is prime-valued for every n from 0 to 79. (However, it is lacking in aesthetic appeal because it is nonmonotonic and it repeats; that is, for n = 0, 1, ? 79, n2 - 79n + 1601 = 1601, 1523, 1447, ? 43, 41, 41, 43, ? 1447, 1523, 1601.)

In spite of this success, it is now known that there is no polynomial f(n) that produces a prime for every n (aside from constant polynomials such as f(n) = 5). In fact, any nontrivial "polynomial in exponentials" is composite infinitely often. More precisely, as stated in [H&W],

Theorem. If f(n) = P(n, 2n, 3n, ? kn) is a polynomial in its arguments, with integral coefficients, and f(n) when n , then f(n) is composite for an infinity of values of n.

Thus, a formula such as n2 ?2n + 2n3 + 2n + 5 must produce an infinite number of composites. On the other hand, the theorem says nothing about formulas containing terms such as graphics/16icon09.gifnn, and n!.

A formula for the nth prime in terms of n can be obtained by using the floor function and a magic number

graphics/16icon10.gif

 

The number a is, in decimal, the first prime written in the first place after the decimal point, the second prime written in the next two places, the third prime written in the next three places, and so on. There is always room for the n th prime, because pn < 10n. We will not prove this, except to point out that it is known that there is always a prime between n and 2n (for n 2), and hence certainly at least one between n and 10n, from which it follows that pn < 10n. The formula for the nth prime is

graphics/16icon11.gif

 

where we have used the relation 1 + 2 + 3 + ? + n = (n2 + n)/2. For example,

graphics/16icon12.gif

 

This is a pretty cheap trick, as it requires knowledge of the result to define a. The formula would be interesting if there were some way to define a independently of the primes, but no one knows of such a definition.

Obviously, this technique can be used to obtain a formula for many sequences, but it begs the question.