*Euler published the remarkable quadratic formula:*

*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, 40 ^{2} + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.*

*Using computers, 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.*

Basically, we need to find a quadratic equation of the form `n`

which produces maximum number of primes for consecutive values of n. The range of values which ^{2} + an + b `a`

can take is from -999 to 999 and that `b`

can take goes from -1000 to 1000. After we find that perfect/longest quadratic equation which generates the primes we need to find the product of `a`

and `b`

.

Even after solving 26 questions, I haven’t improved as such in my thinking. I mean the first approach which comes to my mind is the donkey approach (yep that’s what I call the approach which requires no thinking). So the approach would be to check all possible combinations of `a`

, `b`

within themselves and check which combination can reach the maximum `n`

generating primes. Make a note of maximum of `n`

, `a`

and `b`

& update them if you find another `n`

greater than the previous one.

I took some time to think of another optimal solution but couldn’t think of any. So I just decided to proceed with this approach for now and maybe after some time I would get any idea or a better solution. So my first raw version of the solution was :

source("/Users/ronakshah/Google Drive/Project Euler/3.Check_if_Prime.R") get_quadratic_primes = function() { max_n = 0 for (a in seq(-999, 999)){ for (b in seq(-1000, 1000)) { n = 0 is_number_prime = TRUE while(is_number_prime) { generate_next_number = n^2 + (a * n) + b print(paste(a, b, n, generate_next_number)) if(generate_next_number > 0) { if(is_prime(generate_next_number)) { n = n + 1 } else { is_number_prime = FALSE if(n > max_n) { max_a = a max_b = b max_n = n print(max_n) } } } else { is_number_prime = FALSE } } } } return(list(max_a = max_a, max_b = max_b, max_primes = max_n)) }

Here, I am using the `is_prime`

function from Problem 3. It just returns whether a particular number is prime or not. Also another interesting thing which I came to know while solving this problem was that negative numbers are never prime. I was a little confused at first as these numbers also had negative numbers, I just confirmed it with a quick search. Also I received a couple of errors while solving this one in my `is_prime`

function. I had not handled the cases for number 1 and 2 which I have added and updated.

Although I wasn’t concerned right now about the time but just to benchmark I checked, it came out to be

# user system elapsed # 192.892 3.167 200.767

This was expected as there were almost 2000 X 2000 iterations with a variable iteration of `n`

. Also for all these numbers we call the `is_prime`

function which further increases the computation. Although this isn’t optimal but it gave me the right answer which was

$max_a [1] -61 $max_b [1] 971 $max_primes [1] 71

This combination of 971 and – 61 produces maximum number of primes for consecutive values of `n`

which is 71.

Now thinking of optimizing this problem I google searched few of the approaches and turns out there is no trick or formula to solve this problem ‘intelligently’. All you can do is reduce some of the iterations which are obvious and not needed.

**Case 1:**

Substituting `n = 0`

in the expression: `n`

we get ^{2} + an + b`0 + 0 + b`

whose answer should be prime which means `b`

is prime. So we should filter only those `b`

’s which are prime.

**Case 2:**

Substituting `n = 1`

in the expression : `n`

, we get ^{2} + an + b`1 + a + b`

whose answer should also be prime. Now prime numbers are always odd (except 2) so for `1 + a + b`

to be prime when `a`

is even, `b`

has to be even to keep the sum as odd. Also when `a`

is odd, `b`

has to be odd to keep the sum odd. By this we would reduce half amount of iterations.

Incorporating these changes, we have

get_quadratic_primes_v3 = function() { max_n = 0 for (a in seq(-999, 999)){ for (b in seq(2, 1000)) { n = 0 if(is_prime(b) & identical(a %% 2, b %% 2)) { is_number_prime = TRUE while(is_number_prime) { generate_next_number = n^2 + (a * n) + b print(paste(a, b, n, generate_next_number)) if(generate_next_number > 0) { if(is_prime(generate_next_number)) { n = n + 1 } else { is_number_prime = FALSE if(n > max_n) { max_a = a max_b = b max_n = n print(max_n) } } } else { is_number_prime = FALSE } } } } } return(list(max_a = max_a, max_b = max_b, max_primes = max_n)) } #user system elapsed #63.822 1.088 67.377

The time reduced drastically from 200 seconds to 67 which is a good achievement in itself.