A Formula for Primes

Consider a polynomial $F(x) = x^{2} + 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\cdot 40 + 40 + 41 = 40\cdot (40 + 1) + 41 = 41^{2}.\,$ Still, it's interesting that $F(x)\,$ is prime for all integers from $1\,$ through $39.$

$G(x) = x^{2} - x + 41\,$ is prime for $x\,$ from $0\,$ through $40,\,$ and $H(x) = x^{2} - 79x + 1601\,$ is prime for $x\,$ from $1\,$ through $80.\,$ $H(81) = 41\cdot 43.\,$ $80\,$ is a long run of primes indeed.

Francisco Javier García Capitán put together the following table

Monic polynomials giving primes

$n^2 + n + 41\,$ gives prime numbers for $n = 0, \ldots, 39.\,$ (Euler, 1772)
$n^2 - n + 41\,$ gives prime numbers for $n = 0, \ldots, 40.\,$ (Legendre, 1798)
$n^2 - 15n + 97\,$ gives prime numbers for $n = 0, \ldots, 47.\,$ $^{(*)}$
$n^2 - 61n + 971\,$ gives prime numbers for $n = 0, \ldots, 70.\,$ $^{(**)}$
$n^2 - 79n + 1601\,$ gives prime numbers for $n = 0, \ldots, 79.\,$
$n^2 - 81n + 1681\,$ gives prime numbers for $n = 1, \ldots, 80.\,$ $^{(***)}$

$^{(*)}$This is a maximum when we consider polynomials of the form $n^2 + an + b,\,$ with $-100 \le a, b \le 100.$
$^{(**)}$This is a maximum when we consider polynomials of the form $n^2 + an + b,\,$ with $-1000 \le a, b \le 1000.$
$^{(***)}$Both of them are maximal when we consider polynomials of the form $n^2 + an + b,\,$ with $-20000 \le a, b \le 20000.$

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:

$\begin{align} &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 \end{align}$

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\cdot 4139.$

In 1992, Michael Goedde discovered that $4^n + 4503$ is prime for $n = 1, \ldots, 14.$

More prime-generating polynomials are listed at Math World.

References

  1. 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
  2. Oystein Ore, Number Theory and Its History, Dover Publications, 1976
  3. J. A. Paulos, Beyond Numeracy, Vintage Books, 1992.
  4. D. Wells, You Are a Mathematician, John Wiley & Sons, 1997

|Contact| |Front page| |Contents| |Generalizations| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

71471708