Duncan's blog

December 10, 2014

Project Euler: problem 27 (PHP) – Quadratic primes

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

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.

Problem 27:

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.

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.

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.

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: