2
$\begingroup$

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$.
$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$ – gnasher729 May 23 '20 at 7:15
  • 1
    $\begingroup$ 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. $\endgroup$ – gnasher729 May 23 '20 at 7:39
1
$\begingroup$

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?

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

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}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.