Here is another project euler challenge that states:

Euler discovered the remarkable quadratic formula:

n^{2}+ n + 41It turns out that the formula will produce 40 primes for the consecutive integer values

0 ≤ n ≤ 39. However, whenn = 40, 40is divisible by 41, and certainly when^{2}+ 40 + 41 = 40(40 + 1) + 41n = 41, 41is clearly divisible by 41.^{2}+ 41 + 41The incredible formula

nwas discovered, which produces 80 primes for the consecutive values^{2}- 79n + 16010 ≤ n ≤ 79. The product of the coefficients, −79 and 1601, is −126479.Considering quadratics of the form:

n, where^{2}+ an + b|a| < 1000and|b| ≤ 1000where|n|is the modulus/absolute value ofn

e.g.|11| = 11and|-4| = 4Find the product of the coefficients,

aandb, for the quadratic expression that produces the maximum number of primes for consecutive values ofn, starting withn = 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, 0*^{2} + 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, 1*^{2} + 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; } } }

Recent Blog Activity

Blog Archive