Challenge: Quadratic Primes

Posted on: June 13, 2017 1:13:31 AM

Here is another project euler challenge that states:

Euler discovered the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive integer values 0 ≤ n ≤ 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.

The incredible formula n² - 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.

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.

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² + 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² + 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;
        }
    }
}

Comments

live gay young male sex chat rooms [url="https://chatcongays.com"]new york gay chat lines[/url] best gay webcam chat
GenniesrPa September 16, 2022 1:49:18 AM

good essay writers [url="https://au-bestessays.org"]write my essay wikipedia[/url] essay writing services scams
MarrissrPa September 20, 2022 12:26:00 AM

buy a essay [url="https://bestcampusessays.com"]buy cheap essays[/url] order custom essays
DorolisasrPa September 20, 2022 7:39:15 PM

national junior honor society essay help [url="https://besteasyessays.org"]write my essays[/url] cheap custom essay papers
MartysrPa September 21, 2022 5:58:57 PM

help me write essay [url="https://bestessayreviews.net"]i need help writing an essay for college[/url] best essay editing service
MerolasrPa September 22, 2022 1:55:13 PM

buy essay papers online [url="https://bestessaysden.com"]mba essay editing service[/url] buy cheap essays online
AshlensrPa September 23, 2022 9:43:52 AM

buy essays online safe [url="https://bestsessays.org"]essays on the help[/url] help writing an essay
CharitasrPa September 24, 2022 11:20:21 PM

college essay help nyc [url="https://buyacademicessay.com"]what are good essay writing services[/url] are essay writing services legal
NanicesrPa September 25, 2022 6:19:13 PM

scholarship essay writing help [url="https://buy-eessay-online.com"]college essay help[/url] help me essay
ChelsaesrPa September 26, 2022 1:58:13 PM

cheap write my essay [url="https://buytopessays.com"]best custom essay writers[/url] best college essay editing service
PennysrPa September 27, 2022 9:06:25 AM

college entrance essay writing service [url="https://cheapessaywritingservice1.com"]critical essay help[/url] help on college essay
TammiesrPa September 28, 2022 4:58:06 AM

essay writing homework help [url="https://customcollegeessays.net"]essay on the help[/url] persuasive essay helper
AntoniesrPa September 29, 2022 12:56:19 AM

write my essay website [url="https://customessays-writing.org"]buy essay[/url] essays services
RhiamonsrPa September 29, 2022 8:33:47 PM

cheap essay services [url="https://customessaywwriting.com"]buy essay cheap[/url] buying essay
CharosrPa September 30, 2022 3:26:26 PM

professional custom essays [url="https://customs-essays-writing.org"]custom essay station[/url] write my essay for me cheap
DronasrPa October 1, 2022 10:02:17 AM

essay help introduction [url="https://geniusessaywriters.net"]english essay writing service[/url] writing essays custom
LeilahsrPa October 3, 2022 2:17:31 AM

essay writing services us [url="https://howtobuyanessay.com"]high school essay help[/url] essay editing service reviews
CthrinesrPa October 4, 2022 12:12:01 AM

essay on community service [url="https://lawessayhelpinlondon.com"]essay helper online[/url] essays on community service
GinniesrPa October 9, 2022 12:04:46 PM

buy essay papers [url="https://ukessayservice.net"]best essay writing company[/url] essay writing websites
VivienesrPa October 11, 2022 6:26:34 PM

essay writing service best [url="https://writemyessaycheap24h.com"]college essay writing service reviews[/url] cheap essays
EastersrPa October 13, 2022 9:24:20 AM

best online essay editing service [url="https://besteasyessays.org"]write my essay students[/url] buy essays
MartysrPa November 20, 2022 1:06:34 PM

writing essay services [url="https://bestessayreviews.net"]cheap custom essay writing services[/url] college essay helper
MerolasrPa November 21, 2022 8:55:44 PM

mba essay writing service [url="https://bestessaysden.com"]professional college essay writers[/url] cheap essays online
AshlensrPa November 23, 2022 5:49:37 AM

english essay helper [url="https://bestsessays.org"]live essay help[/url] buy essay papers
CharitasrPa November 24, 2022 1:30:14 PM

college admission essay help [url="https://buyacademicessay.com"]admission essay editing services[/url] the best essay writer
NanicesrPa November 25, 2022 10:47:23 PM

famous essay writers [url="https://buy-eessay-online.com"]sat essay writing help[/url] expository essay help
ChelsaesrPa November 27, 2022 8:07:45 AM

write my admission essay [url="https://buytopessays.com"]college application essay service[/url] us essay writers
PennysrPa November 28, 2022 5:18:35 PM