# 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$$?

• 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$$.
• Just an observation. If a < 2,000 then you get a much longer sequence than the one with a = -1, b=41 (primes are the same). – gnasher729 May 23 '20 at 7:15
• You could build a sieve that is large enough for n=20, and use trial division if n^2+an+b is too large for the sieve - which will be rare. – gnasher729 May 23 '20 at 7:39

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 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?

• Thanks for concluding that the $D<0$ condition is not correct. Also, I already figured out that $a$ needs to be odd. – impopularGuy May 23 '20 at 2:25

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}$$.

$$$$f(ax+by)=a^2(x^2+x)+aby(2x+1)+b^2y^2+b$$$$ 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 $$$$n = b\left( \left\lfloor \frac{a}{b} \right\rfloor +1 \right)-a$$$$ 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} n0 \end{cases}$$

In order to keep $$f(n)$$ always positive, we need $$$$n\notin \left[(-a-\sqrt{a^2-4b})/2,(-a+\sqrt{a^2-4b})/2 \right]$$$$ 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 $$$$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}$$$$