<s>[INST] Is there a way to find an upper bound for $n^2+an+b$? 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$.

 [/INST] 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}
</s>