# Prime rich quadratic polynomials?

Definition

I want to find terms of the sequence that are the next smallest $A_n\in\mathbb N$ such that $f_{A_n}(x)=x^2+x+A_n$ is the prime richest quadratic polynomial so far; meaning it is richer in primes that all previous $f_{A_m},m\lt n,$ for all $x$ greater than some sufficiently large $x_0$.

If $\pi_A(n)$ is the number of primes produced by $f_A$ for $0\le x\le n$, then we say that
$f_{A_1}$ is prime richer than $f_{A_2}$ at $n$ if: $\pi_{A_1}(n)\gt\pi_{A_2}(n) \text{ or } \pi_{A_1}(n)=\pi_{A_2}(n) \text{ and } A_1\lt A_2$ .

Searching for terms

Computing $\pi_A(10^5)$ for all $A\le41$ seems to imply that sequence starts as: $1,7,11,17,41,\dots$

All odd $A\le41$ sorted by "prime richness" based on (sufficiently large?) $\pi_A(10^5)$ below:

$$33, 15, 9, 21, 39, 3, 27, 13, 35, 19, 5, 25, 23, 1, 7, 31, 29, 37, 11, 17, 41$$

And the plot of $\pi_A(n)$ of these can be seen here for $n=0\dots10^5$, where $\pi_A$ that are less than $\pi_1$ are colored in gray,black and pink, and both $\pi_1$ and $\pi_{41}$ are colored in red.

For next terms there are candidates $\dots,21377, 27941, 41537, 55661,\dots$ based on a comment from this OEIS entry; where I'm not sure why $154001$ is also mentioned as next best term after $55661$, since it does worse than the rest mentioned, in terms of $\pi_A(n)$; I suspect it is a typo?

These are only candidates because I'm not sure whether there are terms missing in between them; I suspect there might be terms in between $41,\dots,21377$, as I haven't started computing $\pi_A(n)$ for large enough $n$ yet, for $A\gt41$. But interestingly, they both are not far away on the graph in prime richness, so far.

I have plotted $\pi_A(n)$ for $n=0\dots10^5$ for all mentioned terms above:

The gap in prime richness between $f_{17},f_{41}$ is interesting.

Cyan and blue ($f_{27941},f_{41537}$) are seemingly overlapping, and it appears to be the same case as yellow,orange $(f_1,f_7)$; it's not clear if one is prime richer than the other, which is discussed next for the smaller case.

Uncertainty among $1$ and $7$

Notice $f_1,f_7$ seem to overlap, but $\pi_7$ beats $\pi_1$ with $10788\text{ to }10751$ primes, at $n=10^5$. Seems like $f_7$ is always better than $f_1$ for all $n\ge12756$, but only slightly, which accumulates to only a $37$ primes difference at $n=10^5$ as already mentioned.

I continued to compute $\pi_A(n)$ up to $n=10^6$ because it seemed like $f_1$ could overtake $f_7$ again.

Indeed, at $n=120939$, $f_1$ overtakes in prime richness, and $\pi_1,\pi_7$ keep interchanging until $n=157782$, where $\pi_7$ continues the lead again with a fluctuating slight prime advantage.

At $n=750573$, $f_1$ again overtakes in prime richness and $\pi_1,\pi_7$ continue interchanging the lead again. But surprisingly, after $n=846279$, $\pi_1$ now overtakes lead for the first time for a longer period which is up to $10^6$ so far and counting.

Exact standings so far are: $\pi_1(10^6)=88118$ and $\pi_7(10^6)=88106$, only $12$ primes difference.

Seems like computing larger $\pi_A(n)$ here won't help.

Now I'm not sure whether there exists some sufficiently large $n_0$ such that $\pi_7(n)\gt\pi_1(n)$ for all $n\ge n_0$? Is it possible to show if this is the case or not?

Since this, by initial definition, says whether the sequence starts as $1,7,11,17,41$ or $1,11,17,41$

Computing more terms

I wanted to do a "brute force" and compute $\pi_A(n)$ for all odd $A$ in between the candidate terms so far up to some large $n$ to sort them out and confirm whether terms are missing or not, but this seems like it's taking extremely slow with my naive c++ code. I suspect it is redundant to check composite $A$, but even considering only $A$ that are prime or a product of two primes, it is still very slow going when aiming for larger $n$ and more of $A$'s.

Is it possible to find terms of this sequence efficiently and with more certainty?

Are there software or programming tools once could utilize to perform this task?

What so far is known about prime rich quadratics of form $f_A=x^2+x+A$?

Remark

But even with decent efficiency, computing large $\pi_A(n)$ does not help in cases such as $f_1,f_7$ and $f_{27941},f_{41537}$, which both have interchanging and leading periods. It seems that in both cases we will have interchanging periods occur infinitely many times, but I suspect this is hard to show.

For simplicity, if we have behavior such as $\pi_C\lt\pi_A\approx\pi_B\lt\pi_D$ for all $n$ greater than some sufficiently large $n_0$, where $A\lt B$, then then the sequence goes $\dots,C,A,B,D,\dots$

Thus, so far we would have $1,7,11,17,41,\dots?\dots,21377,27941,41537,55661,\dots$

I'm mainly interested in finding more terms.

• Do you search the record holders, or just other $A$ with a large number of primes ? – Peter Jul 6 '18 at 22:20
• @Peter Just other $A$ with large number of primes: I'm hoping to list and find a sequence of all $A$ that increases in efficiency of producing primes up to some larger term; as the question currently stands: I'm looking into whether there are any terms in between $41,21377$, and primarily how to efficiently get terms coming after $55661$ which is the current largest term closest to the previous terms I've listed. – Vepir Jul 6 '18 at 22:32
• Record holders for $n=1000$ tend to be record holders also for $n=10^5$, the next record holder for $n=1000$ is $247\ 757$ with $657$ primes and in fact for $n=10^5$ we have $39\ 759$ primes – Peter Jul 6 '18 at 23:08
• @Peter I've just stumbled upon this unrelated answer that mentions $247 757$ which has $39759$ primes at $\pi(10^5)$; I've plotted now 55661,115721,247757 for $n=0...10^5$ which are at $(35886,37059,39759)$, and indeed it seems that $115 721$ is very likely the next term after $55661$,! I'm not sure if there could also be a term in between $115721,247757$. – Vepir Jul 6 '18 at 23:10
• @Peter I appreciate your comments and insight! – Vepir Jul 6 '18 at 23:19