Prime-Generating Polynomial

Legendre showed that there is no rational algebraic function which always gives primes. In 1752, Goldbach showed that no polynomial with integer coefficients can give a prime for all integer values (Nagell 1951, p. 65; Hardy and Wright 1979, pp. 18 and 22). However, there exists a polynomial in 10 variables with integer coefficients such that the set of primes equals the set of positive values of this polynomial obtained as the variables run through all nonnegative integers, although it is really a set of Diophantine equations in disguise (Ribenboim 1991). Jones, Sato, Wada, and Wiens have also found a polynomial of degree 25 in 26 variables whose positive values are exactly the prime numbers (Flannery and Flannery 2000, p. 51).

The plot above visualizes the number of primes generated by quadratic polynomials of the form for and from to 200 (M. Trott, pers. comm.).

The best-known polynomial that generates (possibly in absolute value) only primes is

(1)

due to Euler (Euler 1772; Nagell 1951, p. 65; Gardner 1984, p. 83; Ball and Coxeter 1987), which gives distinct primes for the 40 consecutive integers to 39. (, due to Legendre in 1798, gives the same 40 primes for to 40. These numbers are called "Euler numbers" by Flannery and Flannery (2000, p. 47), and the set of them that are prime are termed Euler primes in this work. By transforming the formula to

(2)

primes are obtained for 80 consecutive integers, corresponding to the 40 primes given by the above formula taken twice each (Hardy and Wright 1979, p. 18). If is prime-generating for , then so is .

The following table gives some low-order polynomials that generate (possibly in absolute value) only primes for the first few nonnegative values (Mollin and Williams 1990). Polynomials obtainable from others by substitutions, e.g., the variations on of Legendre and Hardy and Wright, are not included. In the table, d.p. indicates the number of distinct primes generated by the polynomial when values from 0 to are plugged in.

polynomial	prime from 0 to	distinct primes	OEIS	reference
	56	57		Dress and Landreau (2002), Gupta (2006)
	54	55		Wroblewski and Meyrignac (2006)
	49	49		Beyleveld (2006)
	46	47		Wroblewski and Meyrignac (2006)
	45	46		Kazmenko and Trofimov (2006)
	44	45	A050268	Fung and Ruby
	46	43		S. M. Ruiz (pers. comm., Nov. 20, 2005)
	42	43	A050267	Fung and Ruby
	42	43		Speiser (pers. comm., Jun. 14, 2005)
	40	40	A005846	Euler
	39	40		Wroblewski and Meyrignac
	34	35		J. Brox (pers. comm., Mar. 27, 2006)
	61	31		F. Gobbo (pers. comm., Dec. 27, 2005)
	57	29		J. Brox (pers. comm., Mar. 27, 2006)
	28	29	A007641	Legendre (1798)
	23	24		F. Gobbo (pers. comm., Dec. 26, 2005)
	21	22		R. Frame (pers. comm., Dec. 30, 2018)
	19	20		E. Pegg, Jr. (pers. comm., Jun. 14, 2005)
	17	18		A. Bruno (pers. comm., Jun. 12, 2009)
	15	16	A007635	Legendre
	13	14	A048988	Honaker
	10	11	A050265
	10	11	A050266

A particularly poor polynomial is , which isn't prime for , ..., 3905, but which is prime for , 4620, 5166, 5376, 5460, ... (OEIS A066386; Shanks 1971, 1993; Wells 1997, p. 151). Other polynomials of this type include , which was discovered by Carmody in 2006 (Rivera) and is prime for 63693, 64785, 70455, 90993, 100107, ... (OEIS A119276), and , which is prime for 616980, 764400, 933660, ... (OEIS A122131).

Le Lionnais (1983) has christened numbers such that the Euler-like polynomial

(3)

is prime for , 1, ..., as lucky numbers of Euler (where the case corresponds to Euler's formula). Rabinowitz (1913) showed that for a prime , Euler's polynomial represents a prime for (excluding the trivial case ) iff the field has class number (Rabinowitz 1913, Le Lionnais 1983, Conway and Guy 1996). As established by Stark (1967), there are only nine numbers such that (the Heegner numbers , , , , , , , , and ), and of these, only 7, 11, 19, 43, 67, and 163 are of the required form. Therefore, the only lucky numbers of Euler are 2, 3, 5, 11, 17, and 41 (le Lionnais 1983, OEIS A014556), and there does not exist a better prime-generating polynomial of Euler's form. The connection between the numbers 163 and 43 and some of the prime-rich polynomials listed above can be seen explicitly by writing

(4)

(5)

etc.

Euler also considered quadratics of the form

(6)

and showed this gives primes for for prime iff has class number 2, which permits only , 5, 11, and 29. Baker (1971) and Stark (1971) showed that there are no such fields for . Similar results have been found for polynomials of the form

(7)

(Hendy 1974).

Wolfram Web Resources