Programming contest: Prime generating polynomials

[Max]

On 3/22/06, Hugo Pfoertner <all at abouthugo.de> wrote:
> The current round of Al Zimmermann's programming contests is on prime
> generating polynomials. Some members of our group might consider to
> participate. The contest rules can be found at
> http://www.recmath.org/contest/description.php
>
> The OEIS can help to get a few easy points ....

Thanks for the announcement. It pushed me to refresh my knowledge
about prime generating polynomials, especially about Euler's ones.

There was an interesting problem at IMO 1987:
http://imo.math.ca/Exams/1987imo.html (Problem 6)
that settles up an important property of Euler-like polynomials f(x) =
x^2 + x + p and g(x) = x^2 - x + p (note that g(x) = f(-x) = x^2 - x +
p = (x-1)^2 + (x-1) + p = f(x-1) generates the same values for
x=1,2,...,p-1).

The only known values of p satisfying the statement of Problem 6 are
p=2, 3, 5, 11, 17, and 41. MathWorld at
http://mathworld.wolfram.com/LuckyNumberofEuler.html calls these
number "Lucky numbers of Euler" and claims that this list is compete
pointing out a relation with the imaginary quadratic field
Q(sqrt(1-4p)) and its class number. This relation is based (as I
understand) on the following identity
4g(x) = 4x^2 - 4x + 4p = (2x-1)^2 - (1-4p) = (2x-1-sqrt(1-4p)) *
(2x-1+sqrt(1-4p)).

MathWorld says that p is a Lucky number of Euler if and only if the
class number h(1-4p) equals 1 (in this case 1-4p is called Heegner
number, and it is proved that there are only nine such numbers exist:
-1, -2, -3, -7, -11, -19, -43, -67, and -163) and ends up with a
conclusion: ``there does not exist a better prime-generating
polynomial of Euler's form''. I have certain doubts about that.

I believe that if the class number h(1-4p)=1 then the polynomial g(x)
generates primes for x=0,...,p-2.
But I am not convinced about the converse, i.e., why g(x) generating
primes for x=0,...,p-2 implies h(1-4p)=1 ? Could number theory gurus
please clarify that?

At the moment I have two "indirect" counterarguments:

1) In claiming the equivalence of these statements MathWorld provides
three references: Rabinowitz 1913, Le Lionnais 1983, Conway and Guy
1996. I check the last reference and it happens to claim precisely the
following (on p. 225):

``the formula n^2-n+k represents primes for the consecutive numbers
n=1,...,p-1 as long as 1-4k is one of the Heegner numbers''

In other words, it claims if "1-4k is one of the Heegner numbers" then
"the formula n^2-n+k represents primes for the consecutive numbers
n=1,...,p-1" but nothing about the converse!


2) In some russian book (not that old) I have read that the existence
of p other than 2, 3, 5, 11, 17, 41 such that f(x) generates primes
for x=0,...,p-2 is an open problem, and it is proved that there is no
other p for p<10^9. If anybody heard of this problem, please update me
with the current status.
Another related conjecture from the same source: for every n there
exists prime p such that all numbers f(0), f(1), ..., f(n) are prime
for f(x) = x^2 + x + n.

Max