Prime-Generating Polynomial

A prime-generating polynomial is a polynomial that generates prime numbers when its arguments range over a specified set of integers.

Legendre showed that there is no nonconstant rational algebraic function which always gives primes. Goldbach showed that no nonconstant polynomial with integer coefficients can give a prime for all integer values (Nagell 1951, p. 65; Hardy and Wright 1979, pp. 18 and 22; Pollack 2009, p. 15). 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.).

A well-known example 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
	36	36		P. Borghi (pers. comm., Jan. 9, 2026)
	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		Maloth (2016)
	19	20		E. Pegg, Jr. (pers. comm., Jun. 14, 2005)
	17	18		A. Bruno (pers. comm., Jun. 12, 2009)
	16	17	A356727	Delaporte
	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 every integer with iff is squarefree and the field has class number 1 (Rabinowitz 1913, Le Lionnais 1983, Conway and Guy 1996; Pollack 2009, p. 15). The squarefree condition is essential. For example, gives the class-number-one field , but is a composite number. As established by Stark (1967), there are only nine positive integers for which has class number 1 and is squarefree. These Heegner numbers are 1, 2, 3, 7, 11, 19, 43, 67, and 163, of which only 7, 11, 19, 43, 67, and 163 have the required form . Therefore, the only lucky numbers of Euler are 2, 3, 5, 11, 17, and 41 (Le Lionnais 1983, OEIS A014556). Thus no makes prime throughout the entire range . 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).

Radomskii (2026) proved that for every irreducible polynomial of positive degree and positive leading coefficient taking integer values at every integer, there is a constant such that, for every sufficiently large , the interval contains at least consecutive integer arguments at all of which is a composite number. In particular, this applies to .