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.



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

  • $\begingroup$ An upper bound for the number of primes of a polynomial $p(n)$ of the form $ax^n + bx^{n-1} + ... + rx + s$ is $s-1$ (as $s$ always divides $p(s)$). Judging from the table provided by the article though, it seems this bound can be sharpened. $\endgroup$ – Max Muller Dec 5 '10 at 17:42
  • $\begingroup$ The problem, I think, would be more interesting if you required that the polynomial be monic. $\endgroup$ – Qiaochu Yuan Dec 6 '10 at 7:28

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.

  • $\begingroup$ @ Greg Muller: let $f(x)=3x+5$. Then already at $x=1$, we see that $f(x)=8$, not a prime! By Green-Thao's theorem we only know that $f(x)$ will generate infinitely many primes, but now how much primes it will generate after consecutive positive integer values. $\endgroup$ – Max Muller Dec 5 '10 at 18:03
  • $\begingroup$ I don't understand your example. If I know an arithmetic progression of primes of length $n$, then I can produce a degree 1 polynomial whose values at $x=0,1,...n-1$ are exactly that set of primes. So, I get the arithimetic progression as the first $n$ values of my polynomial at non-negative integers. $\endgroup$ – Greg Muller Dec 5 '10 at 18:07
  • $\begingroup$ I just wanted to point out that it doesn't work for every polynomial of degree 1, I'm also interested about the form. Considering your claim: let's take the set of primes {2,3,5,7,11,13}, what polynomial of degree 1 corresponds to those primes for arguments $x=0,1,...,n-1$? $\endgroup$ – Max Muller Dec 5 '10 at 18:14
  • $\begingroup$ That is not an arithmetic progression. To be an arithmetic progression, adjacent elements have to differ by a constant amount. So $\{3,5,7\}$ is an arithmetic progression, since all differences are $2$, but $\{2,3,5\}$ is not. For examples of long strings of primes in arithmetic progression, see: en.wikipedia.org/wiki/Primes_in_arithmetic_progression $\endgroup$ – Greg Muller Dec 5 '10 at 18:17
  • $\begingroup$ Oh ok I wasn't aware of that. Let's take the set {3,5,7} then. We then have the corresponding polynomial f(x)=2x+3 that satisfies of which the value corresponds to the elements at x=0,1,2. If we go on, however, we find that f(3)=9, which isn't prime. So this isn't a very 'succesful' polynomial (<-- thinking out loud here). Hmmm your answer almost feels like cheating, but it's correct (I upvoted it). So this also works for polynomials of degree 2,3,...,n? The question that remains is: how do we figure out what the best form of $p(n)$ is? $\endgroup$ – Max Muller Dec 5 '10 at 18:26

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.


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.

  • $\begingroup$ @ Timothy Wagner: what is a class number? Also, what is $\mathbb{Q}[\sqrt(d)]$? I suppose there are numerous articles explaining such things, but I think I would appreciate a one-to-one explanation much more. $\endgroup$ – Max Muller Dec 5 '10 at 17:53
  • 1
    $\begingroup$ This is really more of a negative result, because there are only a finite number of $d$ such that $\mathbb{Q}[\sqrt{d}]$ has class number 1. Therefore, the best polynomial this approach can produce is give by the polynomial $x^2+x+40$, which corresponds to the last Heegner number 163. $\endgroup$ – Greg Muller Dec 5 '10 at 18:02
  • 2
    $\begingroup$ @Greg Muller: $x^2 + x + 41$. :) $\endgroup$ – Pete L. Clark Dec 6 '10 at 0:09

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:


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.