Grind Report 27

Problem 27

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² + 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.

*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*