Is there a way to find an upper bound for $n^2+an+b$?

Question

I was solving the Project Euler: Problem 27.

Considering quadratics of the form $n^2 + an + b$, where $|a| \lt 1000$ and $|b| \le 1000$

Find the product of the coefficients, $a$ and $b$, for the quadratic expression that produces the maximum number of primes for consecutive values of $n$, starting with $n = 0$.

In order to optimize the algorithm to solve the problem, we can make use of the following fact:

• $b$ must always be prime
• Since $n^2+an+b>0$, Determinant must be negative i.e $D=a^2-4b<0$. This bounds the value of $a$.

I realized that if we predetermine a sieve of Eratosthenes then we can further speed up the process for checking whether $n^2+an+b$ is a prime of not. But, this requires us to find an upper bound to $n^2+an+b$ which is required to generate the sieve.

Substituting $a=\pm2\sqrt{b}$, gives $n^2+an+b = n^2 \pm2\sqrt{b}n+b=(n\pm\sqrt{b})^2 $. However this leads nowhere. Is there a way to find the upper bound for $n^2+an+b$ based on the given conditions for $a$ and $b$?

EDIT: Some additional info.

• If we keep $b$ as primes below 1000 and $|a|<1000$, maximum observed value of $n^2+an+b$ is 12989 at $a=889,b=347,n=14$.
• If we keep $b$ as primes below 1000 and $|a|<\sqrt{4b}$, maximum observed value of $n^2+an+b$ is 1681 at $a=-1,b=41,n=41$.

Answer 1

I would like to extend the answer by @Ingix.

The given quadratic is $f(n)=n^2+an+b$. Let $n=ax+by$ where $x,y \in \mathbb{Z}$.

\begin{equation} f(ax+by)=a^2(x^2+x)+aby(2x+1)+b^2y^2+b \end{equation} If $x^2+x=0$, then $b|f(n)$. This gives $x=0,-1$. For $x=0$, we get $n=by$ and $y=1$ gives the best answer ($y$ cannot be zero otherwise $f(n)$ will be prime).

For $x=-1$, we need $n>0$ i.e. $by-a>0$ i.e. $y> a/b$. Therefore we can say that \begin{equation} n = b\left( \left\lfloor \frac{a}{b} \right\rfloor +1 \right)-a \end{equation} Note that we cannot use $y=\lceil a/b \rceil$ because if $a$ is divisible by $b$, then $n$ will become zero.

However this bound doesn't always work when $a$ is negative. A simple example would be $f_1(n)=n^2-n+3$. Here $f_1(0)=3,f_1(1)=3,f_1(2)=5,f_1(3)=9$. But the bound shows $3\left(\left\lfloor\frac{-1}{3}\right\rfloor+1\right)+1=3(-1+1)+1=1$. So for negative $a$ values, we can use $x=0$.

To sum up, for any pair $(a,b)$ where $b$ is prime and $a$ is odd, an upper bound $n$ is \begin{cases} n<b, & a<0 \ \mathrm{and} \ a\ne -b \\ n<2b, & a<0 \ \mathrm{and} \ a= -b \\ n<b\left(\left\lfloor\frac{a}{b}\right\rfloor+1\right)-a, & a>0 \end{cases}

---

In order to keep $f(n)$ always positive, we need \begin{equation} n\notin \left[(-a-\sqrt{a^2-4b})/2,(-a+\sqrt{a^2-4b})/2 \right] \end{equation} It easy to show that this interval lies on the positive axis only when $a\le-\sqrt{4b}$.

Consider the case where $a=-b$. The lower bound for the interval becomes $(b-\sqrt{b^2-4b})/2$. The lower bound decreases while the interval width increases when $b$ increases, and the lower bound's maximum value is at $b=5$ where the interval itself is $[1.38,3.61]$. It is clear that $n<2$ for any value of $b$ when $a=-b$. Hence, we can ignore the case $a=-b$.

In general a pair $(a,b)$ where $a<-\sqrt{4b}$ can be ignored if it satisfies all the following condition:

• $(-a-\sqrt{a^2-4b})/2$ is less than the current max value of number of consecutive primes.
• The interval for which $f(n)$ is negative contains at least one integer point. This is true only when $\lfloor(-a-\sqrt{a^2-4b})/2\rfloor\ne \lfloor (-a+\sqrt{a^2-4b})/2 \rfloor$.

For the case when $a=-\sqrt{4b}$, the interval is reduced to a point $n=-a/2$ which is not an integer since $a$ is odd. However $a$ will be an integer only when $b$ is a square number which is not possible since $b$ is prime. So we will never encounter this case.

Desmos

---

Finally plugging in optimum values for $a$ and $b$ under given constraints, we get the sieve sizes as \begin{equation} f(n)=\begin{cases} 994009 & n=b,\ a<0,\ a=-1,\ b=997 \\ 994009 & b>a>0,\ a=1,\ b=997 \\ 1985015 & a>b,\ a=999,\ b=997 \end{cases} \end{equation}

Answer 2

Note that your conclusion that the discriminante D must be negative is not correct. Since we only know that $n^2+an+b >0 $ for some non-negative $n$, the parabola that represents the function $f(x)=x^2+ax+b$ could have different negative roots. $n^2+4n+3$ would be a simple example. That means a positive $a$ (together with the positive $b$) is never a contradiction with regard to the function needing to provide positive values for (some) non-negative $n$.

I assume you know that a quadratic function with positve factor before the square term takes it maximal value at either end of the interval of the independent variable. The lower end of the interval, $n=0$ produces $f(0)=b$. So what you need to be concerned about is how big can your $n$ get!

Obviously, $f(b)=b^2+ab+b$ is divisible by $b$. If we assume $f(b)=b$, that leads to $b^2+ab=b(a+b)=0$ and because $b > 0$ we have $a=-b$.

In that case of $a=-b$, it means $n$ could reach $n=b$ and go beyond to produce prime numbers with $f$. But then $f(2b)=4b^2-2b^2+b=2b^2+b > b$ is certainly not a prime any more. But if $a \neq -b$, then we know that $b|f(b)$ and $f(b)\neq b$, so $f(b)$ is not a prime.

To sum up, an upper bound for $n$ is $n<b$ for $a \neq -b$ and $n < 2b$ for $a=-b$.

That means we know that the maximum value $f(n)$ can take is less than $f(b)=b^2+ab+b$ in the former case and $f(2b)=4b^2-2b^2+b=2b^2+b$ in the latter.

Given the constraints of the problem, both values can be bounded from above by $2\cdot1000^2+1000=2,001,000.$

This value is of course much bigger than the constraint on the lower end of the interval $f(0)=b < 1000$.

That means your sieve needs to be done until $2,001,000$. This shouldn't be any problem to calculate and store.

Another small hint for solving: Can an even $a$ produce a "long" list of primes that way?