# Duncan's blog

## December 10, 2014

### Project Euler: problem 27 (PHP) – Quadratic primes

Filed under: PHP,Project Euler — duncan @ 8:00 am
Tags: , ,

Photo by Ianqui Doodle

I’m doing these Project Euler mathematical puzzles as a simple practical exercise for teaching myself PHP, and I’d appreciate any feedback on my code.

Euler discovered 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, 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.

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.

This was another puzzle I’d ignored previously, then looked at it again and realised it wasn’t that hard after all.  First time I’ve really done anything with quadratics since school probably!

```<?php
include 'isPrime.php';

\$maxPrimes = 0;
\$maxCoefficients = [];

calculatePrimes(1, 1);
calculatePrimes(1, -1);
calculatePrimes(-1, 1);
calculatePrimes(-1, -1);

function calculatePrimes(\$incrementA, \$incrementB) {
global \$maxPrimes;
\$a = 0;
while (abs(\$a) < 1000) {
\$b = 0;
while (abs(\$b) < 1000) {
\$n = 0;

while (true) {
\$q = (\$n * \$n) + (\$n * \$a) + \$b;

if (!isPrime(\$q)) {
if (\$n > \$maxPrimes) {
\$maxPrimes = \$n;
setMaxCoefficients(\$a, \$b);
}
break;
}

\$n++;
}
\$b+= \$incrementB;
}
\$a+= \$incrementA;
}
}

function setMaxCoefficients(\$a, \$b) {
global \$maxCoefficients;
\$maxCoefficients = [\$a, \$b];
}

echo \$maxCoefficients[0] * \$maxCoefficients[1];```

So I’ve wrapped up most of the code into one function, which I call four times.  Each time I’m either adding or subtracting 1 from each of the two coefficients.  Then there’s nested loops so we’re going from zero to +/- 999 for both coefficients.  Within that we loop again, incrementing \$n until our quadratic equation doesn’t return a prime number.  At that point, we check if the value of \$n is more than the previous maximum number of primes.  And if it is, I update a global array with those coefficients.

After we finish looping, I then calculate the production from those stored coefficients.  Simple, but not particularly fast.