Prime generating functions
I'm studying prime numbers at school and I've seen some functions that generate mostly prime numbers. I'm talking about : $$\text{Euler's polynomial : } n^2+n+41$$ $$\text{Legendre's polynomial : } 2n^2+29$$ $$\text{Ruby's polynomial : } 103n^2-3945n+34381$$ $$\text{Mersenne numbers : }2^n-1$$
I've noticed a strange correspondence between these functions : they are all second degree polynomials (exept for Mersenne numbers). But Mersenne numbers can also be related by the exponentiation of base 2. So my question is : what is the link between 2 and prime numbers the make these function generating primes? I mean why using a 3rd ,4th degree polynomials or anything else doesn't work?
$\endgroup$ 43 Answers
$\begingroup$There is no reason to assume that there is a dependence between primes, prime generating functions/polynomials and the number 2 as such.
For example gives examples of polynomials of various degrees generating primes.
Another interesting page to take a look at is
$\endgroup$ $\begingroup$It can be proven that almost all values of each of these functions is composite, in the sense that for any positive fraction $\varepsilon$ there is some $N$ such that for any $n>N$ at most $n\varepsilon$ of the values $1,\ldots,n$ produce a prime in any of the four.
I would say that the link between low-degree polynomials and otherwise low-complexity functions is that we're more inclined to look for them than more complicated expressions. Similar things could be said about 47th-degree polynomials but who wants to search that space?
$\endgroup$ $\begingroup$Goetgheluck states that some cubic prime generating polynomials are $x^3 - 34x^2 + 381 x - 1511$ and $ 2x^3 - 45x^2 + 331 - 3191$.
You can improve on these slightly.
$\endgroup$ 1
