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$.
Best Answer
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?