Project Euler Problem 27: Quadratic Primes

Question:

Euler discovered the remarkable quadratic formula:

n2 + 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, 412 + 41 + 41 is clearly divisible by 41.

The incredible formula  n2 − 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 ne.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.

Related Tags:

Brain storm to Brute force

When approaching a problem like this, you should start by talking out loud. Keep brainstorming ideas so that you can get your brain going. If nothing appears in your head, write down the brute force approach.

Let's go through this step-by-step.

Quadratic Formula?

Perhaps one way of brainstorming is to notice the quadratic equation and think of the quadratic formula. Would the formula help in this case? In this case, we aren't looking for n, and the equation isn't set to 0 so the quadratic equation is irrelevant. However, it's still good to keep your brain rolling by thinking of things like this.

Determining a value if prime

We'll definitely need a way to check if the value is actually prime, so let's make sure we have that helper method.

We've covered several ways to check if a value is prime earlier, so let's use this method.

public static boolean isPrimeSqRoot(int input) {

	if (input == 2) 
		return true;
	if (input <= 1) 
		return false;
	if (input % 2 == 0) 
		return false;

	/** 
	 * Only up to the square root. 
	 *  If there exists a factor between input and sqrt(input)
	 *  then that value will have a corresponding factor between 3 and sqrt(input)
	 */
	for (int i = input - 2; i >= Math.sqrt(input); i -= 2) {
		if (input % i == 0) 
			return false;
	}

	return true;
}

Basically this uses the property that if our input value is composite (not prime), then there exists one factor between 0 and sqrt(input) and a corresponding factor between sqrt(input) and input

Brute Force

There comes a time when you need to start jotting down the brute force method just to gauge your understanding and help brainstorm even more. If we write this out, we have values from -999 to 999 for a and the same for b. We calculate each value starting from n = 1 until we hit a non-prime.

We have to do this for all values so we have O(a*b*n) time, where the n here is the value that n can go to without making our equation be composite.

brute force method for quadratic primes in O(n3) algorithm

Plug and chug!

Let's try plugging in numbers to see if we can find any special methods. We start with n = 0.

n2 + an + b = b

We find that b itself must be prime in order for n to pass n = 0. Since b has to be prime, we can say that b must be a positive odd number.

Let's try n = 1.

n2 + an + b = 1 + a + b

We learned earlier that b must be odd. If we plug in any odd numbers for b into the equation above, we must have an odd value for a to make the entire sum prime. This is because all primes except 2 are odd.

So now we have that all values of a and b must be odd for n to be greater than 1.

Full code implementation in Java

Here's the full code in Java. We broke it down into three methods: one that finds the maximum quadratic prime values for a and b, which calls on another function that finds the maximum value of n, which calls another to check if the value is prime.

public class QuadraticPrimes {

	public static void main(String[] args) {

		System.out.println(maxQuadPrime());

	}

	public static int maxQuadPrime() {

		int maxN = 0;
		int maxA = 0;
		int maxB = 0;

		int currentMax = 0;

		for (int a = -999; a < 1000; a += 2) {
			for (int b = 3; b < 1000; b += 2) {
				currentMax = findMaxN(a,b);
				if (currentMax > maxN) {
					maxN = currentMax;
					maxA = a;
					maxB = b;
				}
			}
		}

		return maxA * maxB;
	}

	public static int findMaxN(int a, int b) {

		int max = 0;
		int n = 2;

		while (isPrime(n*n + a*n + b)) {
			if (n > max)
				max = n++;
		}

		return max;
	}

	public static boolean isPrime(int input) {

		if (input == 2) 
			return true;
		if (input <= 1) 
			return false;
		if (input % 2 == 0) 
			return false;

		/** 
		 * Only up to the square root. 
		 *  If there exists a factor between input and sqrt(input)
		 *  then that value will have a corresponding factor between 3 and sqrt(input)
		 */
		for (int i = input - 2; i >= Math.sqrt(input); i -= 2) {
			if (input % i == 0) 
				return false;
		}

		return true;
	}
}

References

Project Euler - Question 27

Came up with a better solution or have a question? Comment below!

Next Challenge: FizzBuzz