Problem 27

Problem 27: Quadratic primes

Euler discovered the remarkable quadratic formula: $$ n^2 + n + 41 $$

It turns out that the formula will produce 40 primes for the consecutive integer values $ 0 \le n \le 39 $ However, when $n = 40, 4- ^2 + 40 = 41 = 40(40 + 1) + 41 $is divisible by 41, and certainly when $n = 41, 41^2 + 41 + 41$ is clearly divisible by 41.

The incredible formula $n^2 -79n + 1601$ waas discovered, which produces 80 primes for the consecutive values $0 \le n \le 79$. The product of the coefficients, -79 and 1601, is -126479.

Considering the quadractics of the: $$ n^2 + an + b$$, where $\vert a\vert < 10000$ and $\vert b\vert \le 1000$

where value $\vert n \vert$ is the modulus/absolute value of n

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

Algorthim:

Interesting problems. I solved this many months back, now looking back at my algorthim, it's not terrible The maian conditions are definitely there, but execution was sub-par

Anyhow, there are 2 main condition that will heelp us nararow down the search

The quadractic must be a real number at all times. Hence, $$ n^2 + an + b > 0 $$ Using quadratic formula, we get $$ \frac{-a \,\, \pm \sqrt{a^2 - 4b}}{2} $$ We see that $a^2 - 4b$ must be positive. However, this doesn't realaly tell us much....
Another approach is to consider that n = 1 is solution. Then, a + b + 1 > 0. Hence, we can set a limit to a, given that b is a prime. We could have done 1 or 2 or 3 as the max number of solutions... Well, I think we could have. But I chose this limit
Lastly, a must be odd. We know n can be odd or even. Hence, the quadratic must choose an $a$ that makes the quadractic odd since primes are odd (except 2). So, if n is even, then $n^2$ is also even, but b is odd. So, we need $an$ to be even. Hence, a can be odd or even. Consider whne n is odd. Then $n^2$ is odd, and b is odd. So, $an$ must be odd. Since n is odd, a must be odd. If it was even, $an$ would be even.

Using thesee two restrictions, we can find the a, b that yields the answer

I shouldn't have used Fermat() function again as it takes a lot longer than just simply generating primes using Sieve and checking if each prime is in this array of primes generated by Sieve.

Code:

Result:


                        Answer: -59231
                        
Runtime: 38 seconds