n² + n + 41
It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.
The incredible formula n² − 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, −79 and 1601, is −126479.
Considering quadratics of the form:
n² + an + b, where |a| < 1000 and |b| < 1000
where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |−4| = 4
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.
Therefore I figured that the most straight forward and inelegant method was to produce a 1999 by 1999 array with individual elements of the array corresponding to the maximum number of consecutive primes generated by that combination of a and b.
Thus the initial element of the array in position |1,1| would be the maximum number of consecutive primes generated by n² + (-999)n + (-999), and the final position of |1999,1999| would be n² + (999)n + (999).
With this plan in mind I tried to think up a quick way to calculate the maximum number of consecutive primes for a given a and b.
I started by having Mathematica generate the first 101 values from the example given in the problem by using a=1 and b=41.
This method is horribly inelegant, however it also does work so it's time to see if I can use this method to generate the 1999 by 1999 array I initially planned for.
I begin by trying a smaller array and seeing if my method works.
To find the maximum element of this array I then use the Position and Max commands. Position gives the location in an array of a specified value, and Max gives the largest element of the array.
One area of concern going forward is that it takes 0.655204 secs for Mathematica to create the 51 by 51 array I used above. Since a 1999 by 1999 array is nearly 1600% larger than a 50 by 50 array that means that generating a 1999 by 1999 array should take at least 17 minutes and 28.33 second. Most likely longer considering that the edges of the array will be dealing with a and b values greater than 900.
Still I have free time and I'm not paying for processing time so we might as well go forward and see how long it takes.
And we thus have our answer for Problem 27.
Now how could we have improved this process.
We could start by recognizing that b has to be a prime number. It was only after I had finished this problem that I realized that since n starts at 0 the first element will always be 0*0 + a*0 + b. Since there are 168 primes less than 1000 that means I only needed 168 rows instead of 1999.
A 1999 by 168 array is 8.4% the size of a 1999 by 1999 array and only took Mathematica 1 minute and 56 seconds to calculate.
Using the following code I can just check if the n values are prime and stop when a non-Prime is found.
Using both methods together the entire process of generating the 1999 by 168 array takes 10 seconds.
I started by creating a rather inelegant method for finding the number of consecutive primes generated on a 1999 by 1999 matrix. This method took 21 minutes and 14 seconds.
I next examined the problem more closely and found areas that could be refined so that I found that same solution in 10 seconds.
I'm confident that the majority of the improvement in performance came from optimizing the operation that found the number of consecutive primes.
This was a longer write up than I originally expected, but it was a rather involved problem that benefited greatly from optimization.