Editing Formula for primes (section)

==Prime formulas and polynomial functions==

It is known that no non-[[constant polynomial]] function ''P''(''n'') with integer coefficients exists that evaluates to a prime number for all integers ''n''. The proof is as follows: suppose that such a polynomial existed. Then ''P''(1) would evaluate to a prime ''p'', so <math>P(1) \equiv 0 \pmod p</math>. But for any integer ''k'', <math>P(1+kp) \equiv 0 \pmod p</math> also, so <math>P(1+kp)</math> cannot also be prime (as it would be divisible by ''p'') unless it were ''p'' itself. But the only way <math>P(1+kp) = P(1) = p</math> for all ''k'' is if the polynomial function is constant.
The same reasoning shows an even stronger result: no non-constant polynomial function ''P''(''n'') exists that evaluates to a prime number for [[almost all]] integers ''n''.

[[Leonhard Euler|Euler]] first noticed (in 1772) that the [[quadratic polynomial]]

:<math>P(n) = n^2 + n + 41</math>

is prime for the 40 integers ''n'' = 0, 1, 2, ..., 39, with corresponding primes 41, 43, 47, 53, 61, 71, ..., 1601.  The differences between the terms are 2, 4, 6, 8, 10... For ''n'' = 40, it produces a [[square number]], 1681, which is equal to 41&thinsp;×&thinsp;41, the smallest [[composite number]] for this formula for ''n'' ≥ 0. If 41 divides ''n'', it divides ''P''(''n'') too. Furthermore, since ''P''(''n'') can be written as ''n''(''n'' +&thinsp;1) + 41, if 41 divides ''n'' +&thinsp;1 instead, it also divides ''P''(''n''). The phenomenon is related to the [[Ulam spiral]], which is also implicitly quadratic, and the [[class number (number theory)|class number]]; this polynomial is related to the [[Heegner number]] <math>163=4\cdot 41-1</math>. There are analogous polynomials for <math>p=2, 3, 5, 11 \text{ and } 17</math> (the [[lucky numbers of Euler]]), corresponding to other Heegner numbers.

Given a positive integer ''S'', there may be infinitely many ''c'' such that the expression ''n''<sup>2</sup> + ''n'' + ''c'' is always coprime to ''S''.  The integer ''c'' may be negative, in which case there is a delay before primes are produced.

It is known, based on [[Dirichlet's theorem on arithmetic progressions]], that linear polynomial functions <math>L(n) = an + b</math> produce infinitely many primes as long as ''a'' and ''b'' are [[relatively prime]] (though no such function will assume prime values for all values of ''n''). Moreover, the [[Green–Tao theorem]] says that for any ''k'' there exists a pair of ''a'' and ''b'', with the property that <math>L(n) = an+b</math> is prime for any ''n'' from 0 through ''k''&nbsp;−&nbsp;1. However, {{as of|2020|lc=y|post=,}} the best known result of such type is for ''k'' = 27:

:<math>224584605939537911 + 18135696597948930n</math>

is prime for all ''n'' from 0 through 26.<ref>[https://www.primegrid.com/download/AP27-81292139.pdf PrimeGrid's AP27 Search, Official announcement], from [[PrimeGrid]]. The AP27 is listed in [http://primerecords.dk/aprecords.htm "Jens Kruse Andersen's Primes in Arithmetic Progression Records page"].</ref>  It is not even known whether there exists a [[univariate polynomial]] of degree at least 2, that assumes an infinite number of values that are prime; see [[Bunyakovsky conjecture]].