# PROBLEM STATEMENT

To explore a more difficult (and therefore more interesting problem), we will jump ahead to the 27th problem on the site. Unlike our previous problems, the description for this one is a bit more involved:

“Euler discovered the remarkable quadratic formula:

It turns out that the formula will produce 40 primes for the consecutive values = 0 to 39. However, when = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when = 41, is clearly divisible by 41.

The incredible formula was discovered, which produces 80 primes for the consecutive values to 79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

, where and and is the modulus/absolute value of , 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 , starting with .”

# SOLUTION STRATEGY

To start, we can observe that if we allow for all the values of and then we have an enormous sample space that will likely not compile and solve in less than 1 minute. As such, we should use some mathematical insight to narrow down the problem so that we can find a solution quickly. Let . In order to have the longest chain of primes it must be the case that, at the least, ** should be prime**. Thus, we have that needs to be prime. This cuts down on the number of values of significantly!

At the same time, we expect that should also be prime. We note that since the prior constraint made it so that should be prime it follows that is either 3 or it is an even number larger than 3. This is because the only even prime is 2, while every other prime is odd. In the first case, in order for to be odd, must be even. In the second case, must be an odd number. Note that these two conditions together imply that .

We have imposed some reasonable restrictions on our two values. Now all we need is an algorithm that will find the values for and that will yield the largest number of consecutive primes. Our algorithm will be:

- Generate the set of primes less than or equal to 1000. This will be the set that we define b from.
- For a given fixed value of b, consider all values of such that and . For the first value of in this set, test the function where . If the value is prime, then increment the number of found primes by 1 and increment to the next value of for the given parameters. If the value is not prime, move on to the next set of parameters. That is, if there are more values of to be tested then do so, otherwise move on to the next value of .

# R IMPLEMENTATION

Time to implement this solution in R! The first thing we need is a function to represent the function value for a given set of parameters. This is easily written:

f <- function(a,b,n) {return(n^2+a*n+b)}

While we can leverage our Sieve function that was mentioned in the post on Primes and Sieves to generate the primes from 1 to 1000, it could be the case that the function evaluates to some prime that is larger than that range. As such, we will want to have a separate function to test whether a given number is prime or not.

IsPrime <- function (N) { if (N < 0) {return(FALSE)} if (N == 1) return (FALSE) if (N == 2 || N == 3) return (TRUE) if (N %% 2 == 0 || N %% 3 == 0) return (FALSE) Start = 5 Stop = ceiling(sqrt(N)) while (Start <= Stop) { if (N %% Start == 0) return (FALSE) Start = Start + 2 } return (TRUE) }

Finally, we need a block of code to manipulate these objects:

ptm <- proc.time() primes = SieveOfErat(1000) largestNumPrimes = 2 a_final = 0 b_final = 0 for(i in 1:length(primes)) { b = primes[i] for(j in (-1000):(1000)) { n = 2 currentNumPrimes = 2 if((j + b) %% 2 != 0) {next} a = j while(IsPrime(f(a,b,n))) { n = n + 1 currentNumPrimes = currentNumPrimes + 1 } if (largestNumPrimes < currentNumPrimes) { a_final = a b_final = b largestNumPrimes = currentNumPrimes } } } print(a_final*b_final) proc.time() - ptm

The result we get is the correct one, **-59,231** (obtained with and ) and this solution gets it in **10.34 seconds**. I am sure there could be room for improvement here on the implementation to make this run faster; consider it a challenge for the interested reader! 🙂