TOPICS
Search

Prime-Generating Polynomial

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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).

PrimeGeneratingPolynomials

The plot above visualizes the number of primes generated by quadratic polynomials of the form x^2+ax+b for a and b from -200 to 200 (M. Trott, pers. comm.).

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

n^2+n+41,
(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 n=0 to 39. (n^2-n+41, due to Legendre in 1798, gives the same 40 primes for n=1 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

n^2-79n+1601=(n-40)^2+(n-40)+41,
(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 p(x) is prime-generating for 0<=x<=n, then so is p(n-x).

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 n^2-n+41 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 n are plugged in.

polynomialprime from 0 to ndistinct primesOEISreference
1/4(n^5-133n^4+6729n^3-158379n^2+1720294n-6823316)5657Dress and Landreau (2002), Gupta (2006)
1/(36)(n^6-126n^5+6217n^4-153066n^3+1987786n^2-13055316n+34747236)5455Wroblewski and Meyrignac (2006)
n^4-97n^3+3294n^2-45458n+2135894949Beyleveld (2006)
n^5-99n^4+3588n^3-56822n^2+348272n-2863974647Wroblewski and Meyrignac (2006)
-66n^3+3845n^2-60897n+2518314546Kazmenko and Trofimov (2006)
36n^2-810n+27534445A050268Fung and Ruby
3n^3-183n^2+3318n-187574643S. M. Ruiz (pers. comm., Nov. 20, 2005)
47n^2-1701n+101814243A050267Fung and Ruby
103n^2-4707n+503834243Speiser (pers. comm., Jun. 14, 2005)
n^2-n+414040A005846Euler
42n^3+270n^2-26436n+2507033940Wroblewski and Meyrignac
43n^2-537n+29713435J. Brox (pers. comm., Mar. 27, 2006)
8n^2-488n+72436131F. Gobbo (pers. comm., Dec. 27, 2005)
6n^2-342n+49035729J. Brox (pers. comm., Mar. 27, 2006)
2n^2+292829A007641Legendre (1798)
7n^2-371n+48712324F. Gobbo (pers. comm., Dec. 26, 2005)
3n^2+3n+232122R. Frame (pers. comm., Dec. 30, 2018)
n^4+29n^2+1011920E. Pegg, Jr. (pers. comm., Jun. 14, 2005)
3n^2+39n+371718A. Bruno (pers. comm., Jun. 12, 2009)
n^2+n+171516A007635Legendre
4n^2+4n+591314A048988Honaker
2n^2+111011A050265
n^3+n^2+171011A050266

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

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

n^2+n+p
(3)

is prime for n=0, 1, ..., p-2 as lucky numbers of Euler (where the case p=41 corresponds to Euler's formula). Rabinowitz (1913) showed that for a prime p>0, Euler's polynomial represents a prime for n in [0,p-2] (excluding the trivial case p=3) iff the field Q(sqrt(1-4p)) has class number h=1 (Rabinowitz 1913, Le Lionnais 1983, Conway and Guy 1996). As established by Stark (1967), there are only nine numbers -d such that h(-d)=1 (the Heegner numbers -1, -2, -3, -7, -11, -19, -43, -67, and -163), 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

x^2+x+41=(x+1/2)^2+(163)/4
(4)
x^2+x+11=(x+1/2)^2+(43)/4,
(5)

etc.

Euler also considered quadratics of the form

2x^2+p
(6)

and showed this gives primes for x in [0,p-1] for prime p>0 iff Q(sqrt(-2p)) has class number 2, which permits only p=3, 5, 11, and 29. Baker (1971) and Stark (1971) showed that there are no such fields for p>29. Similar results have been found for polynomials of the form

px^2+px+n
(7)

(Hendy 1974).

See also

Bouniakowsky Conjecture, Class Number, Euler Polynomial, Euler Prime, Heegner Number, Lucky Number of Euler, Prime Arithmetic Progression, Prime Diophantine Equations, Schinzel's Hypothesis

Explore with Wolfram|Alpha

References

Abel, U. and Siebert, H. "Sequences with Large Numbers of Prime Values." Am. Math. Monthly 100, 167-169, 1993.Baker, A. "Linear Forms in the Logarithms of Algebraic Numbers." Mathematika 13, 204-216, 1966.Baker, A. "Imaginary Quadratic Fields with Class Number Two." Ann. Math. 94, 139-152, 1971.Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, p. 60, 1987.Boston, N. and Greenwood, M. L. "Quadratics Representing Primes." Amer. Math. Monthly 102, 595-599, 1995.Conway, J. H. and Guy, R. K. "The Nine Magic Discriminants." In The Book of Numbers. New York: Springer-Verlag, pp. 224-226, 1996.Courant, R. and Robbins, H. What Is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, p. 26, 1996.Dudley, U. "History of Formula for Primes." Amer. Math. Monthly 76, 23-28, 1969.Euler, L. Nouveaux Mémoires de l'Académie royale des Sciences. Berlin, p. 36, 1772.Flannery, S. and Flannery, D. In Code: A Mathematical Journey. London: Profile Books, p. 47, 2000.Forman, R. "Sequences with Many Primes." Amer. Math. Monthly 99, 548-557, 1992.Gardner, M. The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, pp. 83-84, 1984.Garrison, B. "Polynomials with Large Numbers of Prime Values." Amer. Math. Monthly 97, 316-317, 1990.Hardy, G. H. and Wright, E. M. An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, 1979.Hendy, M. D. "Prime Quadratics Associated with Complex Quadratic Fields of Class Number 2." Proc. Amer. Math. Soc. 43, 253-260, 1974.Hoffman, P. The Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical Truth. New York: Hyperion, pp. 108-109, 1998.Le Lionnais, F. Les nombres remarquables. Paris: Hermann, pp. 88 and 144, 1983.Mollin, R. A. and Williams, H. C. "Class Number Problems for Real Quadratic Fields." Number Theory and Cryptology; LMS Lecture Notes Series 154, 1990.Nagell, T. "Primes in Special Arithmetical Progressions." §44 in Introduction to Number Theory. New York: Wiley, pp. 60 and 153-155, 1951.Pegg, E. Jr. "Al Zimmermann's Programming Contests: Prime Generating Polynomials." Mar. 13, 2006. http://www.recmath.org/contest/description.php.Pegg, E. Jr. "Math Games: Prime Generating Polynomials." Jul. 17, 2006. http://www.maa.org/editorial/mathgames/mathgames_07_17_06.html.Rabinowitz, G. "Eindeutigkeit der Zerlegung in Primzahlfaktoren in quadratischen Zahlkörpern." Proc. Fifth Internat. Congress Math. (Cambridge) 1, 418-421, 1913.Ribenboim, P. The Little Book of Big Primes. New York: Springer-Verlag, 1991.Rivera, C. "Highly Composite Polynomials." http://www.primepuzzles.net/puzzles/puzz_275.htm.Shanks, D. "A Low Density of Primes." J. Recr. Math. 5, 272-275, 1971.Shanks, D. Ex. 162 in Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, p. 222, 1993.Sloane, N. J. A. Sequences A005846/M5273, A007635, A007641, A014556, A048988, A050265, A050266, A050267, A050268, A066386, A119276, and A122131 in "The On-Line Encyclopedia of Integer Sequences."Stark, H. M. "A Complete Determination of the Complex Quadratic Fields of Class Number One." Michigan Math. J. 14, 1-27, 1967.Stark, H. M. "An Explanation of Some Exotic Continued Fractions Found by Brillhart." In Computers in Number Theory, Proc. Science Research Council Atlas Symposium No. 2 held at Oxford, from 18-23 August, 1969 (Ed. A. O. L. Atkin and B. J. Birch). London: Academic Press, 1971.Stark, H. M. "A Transcendence Theorem for Class Number Problems." Ann. Math. 94, 153-173, 1971.Wells, D. The Penguin Dictionary of Curious and Interesting Numbers. Middlesex, England: Penguin Books, 1997.

Referenced on Wolfram|Alpha

Prime-Generating Polynomial

Cite this as:

Weisstein, Eric W. "Prime-Generating Polynomial." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Prime-GeneratingPolynomial.html

Subject classifications