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

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 '16 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 '16 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 '16 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 '16 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 '16 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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