Prime generating polynomials that stop?

[xilman]

Originally Posted by Wacky

There is, perhaps, a related statement about which we might inquire:

Is there some polynomial such that the primes are dense in the range of the polynomial?

I guess that this is trivially, "yes" because P(x) = 13 is a polynomial and ALL values in the range of that polynomial, in particular the only one, namely 13, are indeed prime.

However, I am really looking for a polymomial that has an infinite number of values in its range.

It was proved something over a centuray ago that the polynomial ax+b, where gcd(a,b) = 1, produces 1/a of all primes.

That is, a linear polynomial can be dense over the primes.

For example, the polynomials 10x+1, 10x+3, 10x+7 and 10x+9 between them produce all the primes (other than 2 and 5, of course) and each asymptotically produces one quarter of the primes.

I hope the proof of the first half of that statement (all primes) is instantly obvious. The proof of the second half (1/4 of the primes each) is distinctly non-trivial, though it surely looks exceedingly plausible even at first glance.


Paul

[Wacky]

Originally Posted by xilman

It was proved something over a century ago that the polynomial ax+b, where gcd(a,b) = 1, produces 1/a of all primes.

I guess that I am asking the opposite question: ax+b generates 1/a of the primes. But is there a polynomial that, of the values generated, consistently generates a proportion of primes that does not asymptotically vanish?

[ewmayer]

Originally Posted by xilman

That the primes are not dense in the integers means that the ratio pi(x)/x, where pi(x) is the number of primes less than x, becomes arbitrarily close to zero as x increases.

A polynomial that generates primes can not possibly generate prime values that are dense in the integers because the primes themselves are not dense in the integers.

To reiterate/clarify/beat-to-death: the question I am asking in this regard is whether it is possible for the outputs of a polynomial to contain a fraction of primes (number of prime values of P(x))/x which is asymptotically greater than the corresponding pi(x)/x, i.e. greater than O(1/log(x)). It seems not, but if not, has this been proven or merely conjectured?

[Wacky]

Originally Posted by ewmayer

The question I am asking in this regard is whether it is possible for the outputs of a polynomial to contain a fraction of primes (number of prime values of P(x))/x which is asymptotically greater than the corresponding pi(x)/x, i.e. greater than O(1/log(x)).

I think that we are, basically, asking the same question.

[grandpascorpion]

xilman, Could you qualify that?

2x+1 produces all primes where gcd(2,b)=1 (barring 2 of course)

Numbers of the for 3x+1 and 3x+2 each produce (roughly?) half of the primes.

[xilman]

Originally Posted by grandpascorpion

xilman, Could you qualify that?

2x+1 produces all primes where gcd(2,b)=1 (barring 2 of course)

Numbers of the for 3x+1 and 3x+2 each produce (roughly?) half of the primes.

Correct.

My earlier statement that ax+b produces 1/a of the primes is wrong

Ho hum. A completely silly mistake, which I should have corrected before posting.

A better statement is that for fixed and for each value of such that , the polynomial asymtotically generates of the primes, where is the number of cases where .

So, for instance, when , there are four values of with and the four polynomials (which have ) each generate one quarter of the primes.


My apologies for the earlier error. I really must spend more time proof reading.


Paul

[gatesco]

On the issue of "negative primes": No prime is a multiple of any other prime (ignoring trivial divisors -1 and 1). The only negative integer that shares some properties with primes is -1, as it is helpful for unique factorization of both signs:

-24 = -1 * 2^3 * 3
-16 = -1 * 2^4
-11 = -1 * 11 // Not prime!!
-6 = -1 * 2 * 3
-1 = -1 // Technically not prime as it has magnitude 1, but can behave like one.
8 = 2^3
47 = 47 // Yay, that is prime.

The quadratic equation 36n^2 - 810n + 2753 is said to be prime for 0<=n<=44. WITH the
condition "possibly in absolute value." The equation really being assessed is
| 36n^2 - 810n + 2753 |, which is technically not a polynomial. The absolute value seems like a cheat for generating a lot of successive prime outputs.

Thus, it's more useful to search for functions with high prime densities, as Jacobsen and Williams have done. The problem is that the average number of solutions modulo each prime for an irreducible polynomial under the Bouniakowsky conjecture tends to 1. In other words, the fraction of the function's outputs that are NOT divisible by a set of primes P is roughly the product of (P - 1) / P for all elements of P. If all primes are included in P, this product tends to zero, so the asymptotic fraction of prime outputs, as the outputs tend to infinity, does approach zero. What a shame. It does approach zero quite slowly, though.

The density values (C) that Jacobsen and Williams present *are* in relation to
pi(x) / x, the prime density of the natural numbers. Since there are lots of quadratics
whose densities exceed 4 in this respect, they can do very well. For 0<=n<=1000000,
quadratic equations such as n^2 + n + 247757 and n^2 + n + 595937 yield over
300000 primes.