Prime generating polynomials that stop?

[R.D. Silverman]

Originally Posted by Primeinator

X^2 + X + 17 also generates a finite series of primes.

No, it does not.

[Pi Rho]

There was a recent competition for prime-generating polynomials that can be reviewed at http://www.recmath.org/contest/PGP/index.php. The polynomial generating the most positive and negative primes for consecutive x (0 to 56) was 1/4 x⁵ - 133/4 x⁴ + 6729/4 x³ - 158379/4 x² + 860147/2 x - 1705829.

[ewmayer]

Are any results known pertaining to whether it is possible for a polynomial with integer coefficients to yield a prime density among its outputs (for consecutive integer values of its argument x) which does not tend to zero as x --> oo?

Note that I'm taking about arithmetic progressions ax + b, for which Dirichlet's theorem guarantees an infinitude of prime outputs if gcd(a,b) = 1 but for which the Prime Number Theorem implies zero asymptotic density of such primes - I'm referring specifically to polynomials of degree >= 2, for which the PNT does not automatically require zero density of prime outputs.

{Added later:}

Ah, doing a little searching allowed me to at least partially answer the question: this is equivalent to a special (single-polynomial) case of the question which the Bateman-Horn conjecture purports to answer (negatively).

For quadratic polynomials this is essentially the famous Hardy-Littlewood Conjecture F, and the prime density must always be asymptotically zero, but can be arbitrarily (but finitely) larger than the Li(x) density of the primes at large. Here's a recent paper from Mathematics of Computation on this topic, "New Quadratic Polynomials With High Densities of Prime Values," by Michael Jacobson and Hugh Williams. Their best numerical result:

Thus, according to Conjecture F and under the assumption of the ERH, we expect the polynomial x2+x-A for A given by
33251810980696878103150085257129508857312847751498190349983874538507313
to have the largest asymptotic density of prime values for any polynomial of this type currently known.

Here's a more-precise statement, excerpted from a preprint of Pieter Moree:

[jinydu]

Originally Posted by ewmayer

Are any results known pertaining to whether it is possible for a polynomial with integer coefficients to yield a prime density among its outputs (for consecutive integer values of its argument x) which does not tend to zero as x --> oo?

Note that I'm taking about arithmetic progressions ax + b, for which Dirichlet's theorem guarantees an infinitude of prime outputs if gcd(a,b) = 1 but for which the Prime Number Theorem implies zero asymptotic density of such primes - I'm referring specifically to polynomials of degree >= 2, for which the PNT does not automatically require zero density of prime outputs.

So what is the concise answer to that question (I don't exactly understand the rest of your post; although I think your answer is no for n = 2)?

[ewmayer]

Originally Posted by jinydu

So what is the concise answer to that question (I don't exactly understand the rest of your post; although I think your answer is no for n = 2)?

Well, assuming the Bateman-Horn conjecture is true, that would imply that all irreducible polynomials f(x) exhibit the [pi(x) proportional to x/log(x)] prime-density asymptotics guaranteed for the primes at large by the PNT, but with the constant of proportionality dependent on the particular polynomial in question (e.g. inversely proportional to deg(f), and also dependent on some other properties of f.)

[jinydu]

In other words, the density of primes for all irreducible (irreducible over what field, by the way?) will decay to zero.

What about reducible polynomials?

[Jens K Andersen]

Originally Posted by mfgoode

First of all let me mention, and I have done so before in this forum, that it has been shown that no polynomial of the from n^2 + n + q with q a prime can do better than the Euler polynomial in giving primes for *succesive* values of n.

More precisely, it has been shown that the lucky numbers of Euler q = 2, 3, 5, 11, 17, 41 are the only values for which n^2 + n + q is prime for n = 0 to q-2. (MathWorld should say n^2+n+q instead of n^2-n+q)

However, it follows from plausible conjectures that n^2 + n + q can be prime for arbitrarily many successive values of n starting at 0.
Finding more than the 40 primes for q = 41 may remain computationally infeasible for decades or centuries. The largest known non-trivial case of "simultaneous primes" is 18.
It's trivial to compute large q for which n^2 + n + q never has a factor below a million or more. Here is a short PARI/GP script to do it.

Originally Posted by ewmayer

Here's a recent paper from Mathematics of Computation on this topic, "New Quadratic Polynomials With High Densities of Prime Values," by Michael Jacobson and Hugh Williams. Their best numerical result:

Thus, according to Conjecture F and under the assumption of the ERH, we expect the polynomial x2+x-A for A given by
33251810980696878103150085257129508857312847751498190349983874538507313
to have the largest asymptotic density of prime values for any polynomial of this type currently known.

Their intended meaning is a little special and not obvious from the paper. A primeform thread discusses this e.g. here and here.
It's trivial to compute larger A which probably has larger asymptotic density, e.g. A = 36212076076372122687442737117503173584640990732801565\
389186570542773865550682348263508926844065951918140635333116\
150569859767059204071025706402682150955722907190895745308118\
511886031925270319147473141837747199 from this post.

[Jushi]

Originally Posted by jinydu

What about reducible polynomials?

Reducible polynomials can only give a finite number of primes, because the factorization of the polynomial gives a factorization of the value.

example for f(x) = (x+1)(x+2):

f(1) = 2 x 3 = 6
f(2) = 3 x 4 = 12
f(3) = 4 x 5 = 20
f(4) = 5 x 6 = 30
...

The value of a reducible polynomial can only be prime if all but one factors are 1 or -1.

[mfgoode]

Originally Posted by R.D. Silverman

No, it does not.

With due regard to your math stature in this forum kindly let me know why you say that the polynomial n^2+n + 17 does not generate a finite prime sequence even though they are nor successive?

As far as I can see it generates primes from 0 -15. The 16th term is 289 which is 17^2.
Mally :coffee.

[victor]

Originally Posted by mfgoode

With due regard to your math stature in this forum kindly let me know why you say that the polynomial n^2+n + 17 does not generate a finite prime sequence even though they are nor successive?

As far as I can see it generates primes from 0 -15. The 16th term is 289 which is 17^2.
Mally :coffee.

Mally, I think the same case as http://www.mersenneforum.org/showpos...7&postcount=18 applies

[S485122]

n^2 + n + 17 generates primes for n in {18, 19, 21, 22, 23, 24, 26, 27, 28, 29, 30, 31, 34, 35, 37, 38, 40, 42, 44, 45, 46, 47, 49, 53, 56, 57, 59, 60, 62, 63, 64, 70, 72, ... , ...} besides the first consecutive values < 16.