9
$\begingroup$

Let $p(n)$ be a polynomial of degree $a$. Start of with plunging in arguments from zero and go up one integer at the time. Go on until you have come at an integer argument $n$ of which $p(n)$'s value is not prime and count the number of distinct primes your polynomial has generated.

Question: what is the maximum number of distinct primes a polynomial of degree $a$ can generate by the process described above? Furthermore, what is the general form of such a polynomial $p(n)$?

This question was inspired by this article.

Thanks,

Max

[Please note that your polynomial does not need to generate consecutive primes, only primes at consecutive positive integer arguments.]

  • 0
    The problem, I think, would be more interesting if you required that the polynomial be monic.2010-12-06

3 Answers 3

12

The Green-Tao Theorem states that there are arbitrarily long arithmetic progressions of primes; that is, sequences of primes of the form $ b , b+a, b+2a, b+3a,... ,b+na $ Since such a progression will be the first $n$ values of the polynomial $ax+b$, this implies that even for degree 1, there is no upper bound to how many primes in a row a polynomial can generate.

  • 0
    Its true that this is a clumsy hammer in practice. As the link in the last comment shows, you have to use astronomical coefficients even to get progressions with 26 primes in a row, which is dwarfed by the 40 primes of Euler's polynomial $x^2+x+40$ (which is degree 2). This demonstrates that to get good prime-generating polynomials, you need to be very, very clever. There is some good stuff here: http://en.wikipedia.org/wiki/Formula_for_primes#Prime_formulas_and_polynomial_functions2010-12-05
4

Here is result by Rabinowitsch for quadratic polynomials.

$n^2+n+A$ is prime for $n=0,1,2,...,A-2$ if and only if $d=1-4A$ is squarefree and the class number of $\mathbb{Q}[\sqrt{d}]$ is $1$.

See this article for details.

http://matwbn.icm.edu.pl/ksiazki/aa/aa89/aa8911.pdf

Also here is a list of imaginary quadratic fields with class number $1$ http://en.wikipedia.org/wiki/List_of_number_fields_with_class_number_one#Imaginary_quadratic_fields

There are many other articles about prime generating (quadratic) polynomials that you can google.

  • 2
    @Greg Muller: $x^2 + x + 41$. :)2010-12-06
1

Here is a related fact which might also be of interest. There exists a polynomial in 26 variables with the property that, if you plug in integers for all 26 variables, and the output is a positive number (it will always be an integer), then the output is prime. The polynomial can be found here:

http://en.wikipedia.org/wiki/Formula_for_primes

Furthermore, every prime occurs as an output of this polynomial. This is a very indirect way to generate primes, because there is no easy way to know if a given input will give a positive output.

There is apparently another polynomial in 10 variables that does this, but Wikipedia doesn't explicitly write it.