Posted on: June 13, 2017 1:13:31 AM
Here is another project euler challenge that states:

Euler discovered the remarkable quadratic formula:

n2 + n + 41

It turns out that the formula will produce 40 primes for the consecutive integer values 0 ≤ n ≤ 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 0 ≤ n ≤ 79. The product of the coefficients, −79 and 1601, is −126479.

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

I tried to find a way to do this outside of brute force, but I couldn't find any fancy formulas or theorems. Knowing that n=0 has to equal a prime number, it was pretty easy to severely narrow down the number of values for b needing to be tested though. n=0, 02 + a(0) + b = b which means b absolutely must be prime. Once you know that b is a prime number, you can also narrow down the values for a by setting n=1. n=1, 12 + a(1) + b = 1 + a + b This result means that, in order to get a prime result, a must be an odd number except when b is 2. This is because all primes, aside from 2, are odd. Knowing this, we can now do a smarter brute force attempt to find the answer.
Program.cs
```using Common.Math;
using System;
using System.Diagnostics;
using System.Linq;

namespace ProjectEuler_27
{
internal class Program
{
private static int[] primeCache = Eratosthenes.GetPrimes(1000).ToArray();

private static bool IsPrime(int num)
{
if (num > primeCache.Last())
{
primeCache = Eratosthenes.GetPrimes(primeCache.Last() * 2);
}

// array.contains checks every value, these are in order from smallest to largest
// so creating our own contains is more efficient.
int i = 0;
while (i < primeCache.Length && primeCache[i] < num)
{
i++;
}

return primeCache[i] == num;
}

private static void Main(string[] args)
{
Stopwatch sw = Stopwatch.StartNew();
ResultHelper result = new ResultHelper();

// 'b' must be prime because when n=0 we get 0^2 + a(0) + b which is just 'b'
// since 0 is inclusive and all results must be prime, we can narrow down 'b' to just prime numbers
int[] bPossibles = primeCache;

// we can also narrow down 'a' possiblities because all primes except for 2 are odd
// so if n=1 we get 1^2 + a(1) + b = 1 + a + b
// since an odd added to an odd is always even, we know that for all cases except 2 'a' must be odd
// in the case of 2 'a' must be even
for (int a = -999; a < 1000; a += 2)
{
for (int bIdx = 0; bIdx < bPossibles.Length; bIdx++)
{
// handle the case of b=2
int workingA = bPossibles[bIdx] == 2 ? a - 1 : a;

int n = 0;
while (IsPrime(Math.Abs(n * n + workingA * n + bPossibles[bIdx])))
{
n++;
}

if (result.Count < n)
{
result = new ResultHelper
{
A = a,
B = bPossibles[bIdx],
Count = n
};
}
}
}

sw.Stop();

Console.WriteLine(\$"{result.Count} primes found in {sw.ElapsedMilliseconds}ms when a={result.A} and b={result.B} with a product of {result.A * result.B}.");
}

private struct ResultHelper
{
public int A;
public int B;
public int Count;
}
}
}
```

No comments yet, be the first to leave one.

Recent Blog Activity
Blog Archive