A Formula for Primes

Consider a polynomial F(x) = x² + x + 41. Let's check its values for a few first integers: F(1) = 43 which is prime. F(2) = 47 which is also prime. Furthermore, F(3) = 53, F(4) = 61, F(5) = 71, F(6) = 83, F(7) = 97, F(8) = 113, F(9) = 131, all of which are prime. Is it right to conclude that F(x) is a prime for all integer x?

Let's check a couple more values: F(10) = 151 is a prime; F(11) = 173 and F(12) = 197 are both prime. However, it's wrong to conclude that F(x) is prime for all integer x. In fact, F(40) = 40·40 + 40 + 41 = 40·(40 + 1) + 41 = 41². Still, it's interesting that F(x) is prime for all integers from 1 through 39.

G(x) = x² - x + 41 is prime for x from 1 through 40, and H(x) = x² - 79x + 1601 is prime for x from 1 through 80. H(81) = 41·43. 80 is a long run of primes indeed.

R.K.Guy gives more examples where patterns seem to appear when looking at several small values of a variable. In some cases patterns are indeed real and valid for other values of the variable; in most cases, as above, they are figments. Guy formulates the Strong Law of Small Numbers:

There aren't enough small numbers to meet the many demands made on them.

These examples may serve as an introduction into the method of Mathematical Induction which consists of two steps. The first is verifying a fact for one value of a variable, say, n. The second is assuming the fact true for an arbitrary value n = k and, on this foundation, proving it for n = k+1. The second step is quite necessary. As examples above demonstrate, verifying a fact for even a large number of particular cases, does not in itself prove the fact in the general case.

There is another interesting example:

3! - 2! + 1! = 5
4! - 3! + 2! - 1! = 19
5! - 4! + 3! - 2! + 1! = 101
6! - 5! + 4! - 3! + 2! - 1! = 619
7! - 6! + 5! - 4! + 3! - 2! + 1! = 4421
8! - 7! + 6! - 5! + 4! - 3! + 2! - 1! = 35,899

Of which all are prime. However, the very next one

9! - 8! + 7! - 6! + 5! - 4! + 3! - 2! + 1! = 326,981

is composite since 326,981 = 79·4139.

References

R. K. Guy, A Strong Law of Small Numbers, in The Lighter Side of Mathematics, R. K. Guy and R. E. Woodrow, eds, MAA, 1994
Oystein Ore, Number Theory and Its History, Dover Publications, 1976
J. A. Paulos, Beyond Numeracy, Vintage Books, 1992.
D. Wells, You Are a Mathematician, John Wiley & Sons, 1997

40615830