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| < 1000where |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.

*WARNING: This contains the solution!*

After reading the question a few times through to make sure I understood it completely I caught onto a subtle hint. In both examples a and b are prime numbers. After thinking about it a little it became obvious that this is necessary to produce a string of prime numbers with n. Such as if b is not prime then n=0 automatically fails. This also concludes that b must be positive.

With this and reusing my prime code I went ahead and solve this problem. I did run into one problem that once I figured it out I realized it was right there in my face the whole time. This was that I am considering all a and b that index the prime numbers up to 1000.

for (int a = 0; primes[a] < 1000; ++a)

I thought that this was clever when I wrote it. But apparently it was too clever for me because later on I completely forgot I was using a and b as an index to the prime numbers. Consequently I wrote the quadratic equation like this...

n * n + a * n + b

instead of indexing the primes array like I was suppose to.

n * n + primes[a] * n + primes[b]

I learned my lesson here. Not to mention that this mistake was a little humbling, I have not made one of these for awhile and so this was much needed. Here is the code. (the IsPrime function is not optimal)

#include <iostream>

using std::cout;

const int MAX = 1000;

const int PRIMECOUNT = 200;

int primes[PRIMECOUNT];

bool IsPrime(long number);

void populatePrimes();

int main()

{

populatePrimes();

int answer = 0;

int highest = 0;

//consider all prime numbers up to 1000 for a

for (int a = 0; primes[a] < MAX; ++a)

{

//also consider the negative version

for (int i = -1; i <= 1; i += 2)

{

int primeA = primes[a] * i;

//consider all prime numbers up to b

for (int b = 3; primes[b] < MAX; ++b)

{

int quadratic;

int n = 0;

//continue calculating the quadratic and checking to see if it is prime

//until it is no longer prime

do

{

quadratic = n * n + primeA * n + primes[b];

++n;

} while (IsPrime(quadratic));

//check to see if the highest n has been reached

if (n > highest)

{

highest = n;

answer = primeA * primes[b];

}

}

}

}

cout << answer;

}

bool IsPrime(long number)

{

for (int i = 0; i < PRIMECOUNT; ++i)

{

if (primes[i] == number)

return true;

if (primes[i] > number)

return false;

}

return false;

}

void populatePrimes()

{

primes[0] = 2;

primes[PRIMECOUNT - 1] = -1;

int number = 3;

int foundCount = 1;

bool isPrime = false;

while (primes[PRIMECOUNT - 1] == -1)

{

//assume a number is prime until proven guilty

isPrime = true;

for (int i = 0; i < foundCount; ++i)

{

//break if the number is divisible by an already found prime number (guilty)

if (number % primes[i] == 0)

{

isPrime = false;

break;

}

//check to see if the current prime number squred is greater than or equal to the provided number

//if so then break. This means the number is a prime.

if (primes[i] * primes[i] >= number)

break;

}

//add the prime number

if (isPrime)

primes[foundCount++] = number;

//increment the number by 2 (to stay odd)

number += 2;

}

}

*saved game*

## No comments:

## Post a Comment