# Methods for searching for prime generating polynomials

I am currently using a non-systematic, pseudo-random method for finding prime-generating polynomials, based on the Bateman-Horn method for finding likely candidates, and then narrowing down. I have been so far, only searching for quadratics, searching up to a depth of only $10$ primes initially with values over $3$, and then refining. I have then been using the quadratic patterns from here with coefficient patterns $+,-,+$ as per the records published therein.

However, I have only been getting max $28$ prime-runs (aside from the expected longer runs associated with the Heegner numbers), searching $10^5$ interations, and then up to $10^6$ $n$ for each quadratic (which is no doubt the downfall, since the resultant runs appear to increase (as expected) the higher the search limit.

Is a more systematic approach more likely to reap better results, or is there a far more efficient method for searching?

eg MMA code thanks largely to @IgorRivin's answer here

Implemeted in stages (eg):

search2[-1, -1, -1]

Most@# & /@ %

With[{a = %}, {hhh[#] & /@ a, searchpt2[#] & /@ a}]

Flatten[Rest@# & /@ %[]]

vv@# & /@ %


Another approach is to maximize to constant $C$ in Bateman–Horn conjecture

The constant is:

$$C = \prod_p \frac{1-N(p)/p}{(1-1/p)}$$

For linear $f(x)$, you can make it unbounded rational.

Let $n\#$ denote primorial, the product of the first $n$ primes.

Let $f_n=n\#x \pm 1$.

$N(p)$ is the number of roots modulo $p$ without multiplicities.

For $p=p_k, k > n$, $N(p)=1$ which makes the term one, so large primes don't change the product.

For $p=p_k, k \le n, N(p)=0$ and the term is $\frac{p}{p-1}$.

The product up to $p_n$ is about $\log{p_n}$ which is unbounded.

• great - thanks - I also noticed that for quadratic $ax^2+bx+c$ for $a$ and $b=n\#$ and $c=1$, the values of $C$ seem to increase without bound too. Is this the case? In any case, thanks for the answer and the link to the paper (built from your original question!) - great stuff - thanks :) Feb 4, 2016 at 18:58
• @martin I suspect something $n\#x^2+n\#x \pm 1$ to be most prime rich quadratics and likely the constant is unbounded too, but can't prove it. One of the reasons is it is never divisible by prime $\le p_n$, which increases the probability of being prime.
• @martin I suspect if you hunt for large primes they might be of practical usage, not sure. My linear is hidden sievieng. For practical usage maybe better is $n\#x^2+1$ since the deterministic primality is faster than the general case.
• @martin If you are experimenting with this, consider looking for prime gap records too. IIRC the quality of the gap is something like $(p_{n+1}-p_n)/\log{p_n}$