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@# & /@ %[[2]]]

vv@# & /@ %

1 Answer 1


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.

For more information about the constant, check @Igor's paper Some experiments on Bateman-Horn

  • $\begingroup$ 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 :) $\endgroup$
    – martin
    Feb 4, 2016 at 18:58
  • 1
    $\begingroup$ @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. $\endgroup$
    – joro
    Feb 5, 2016 at 6:27
  • $\begingroup$ That makes sense. I also suspect that quadratics of that form won't be af much practical use i terms of prime-run searches, as the terms are likely to be too large to test for primality, and search depths would have to be very large indeed. $\endgroup$
    – martin
    Feb 5, 2016 at 8:16
  • $\begingroup$ @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. $\endgroup$
    – joro
    Feb 5, 2016 at 8:43
  • 1
    $\begingroup$ @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}$ $\endgroup$
    – joro
    Feb 5, 2016 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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