Euler 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^(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&sup2; + 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.

Not too hard. All variables tried must be primes. Ugly code, but its damn fast.

import java.util.*;

public class Euler27
{
    public static void main(String[] args)
    {
        System.out.print(“Problem 27:\n”);
        Euler27 e = new Euler27();
        System.out.print(“Answer = ” + e.Problem()+ “\n”);
    }
    public String Problem ()
    {
        ArrayList<Integer> P = new ArrayList<Integer>();
        P = Gen(1000);
        int maxA = 0, maxB = 0, maxN = 0;
        for (int a: P)
        {
            for (int b: P)
            {
                int c = 0;
                for (int n=0; n <= 1000; n++)
                    if (P.contains(n*n + a*n + b))
                        c++;
                    else
                        break;
                if (c > maxN)
                {
                    maxA = a;
                    maxB = b;
                    maxN = c;
                }
            }
            for (int b: P)
            {
                int c = 0;
                for (int n=0; n <= 1000; n++)
                    if (P.contains(n*n + a*n – b))
                        c++;
                    else
                        break;
                if (c > maxN)
                {
                    maxA = a;
                    maxB = -b;
                    maxN = c;
                }
            }
        }
        for (int a: P)
        {
            for (int b: P)
            {
                int c = 0;
                for (int n=0; n <= 1000; n++)
                    if (P.contains(n*n – a*n + b))
                        c++;
                    else
                        break;
                if (c > maxN)
                {
                    maxA = -a;
                    maxB = b;
                    maxN = c;
                }
            }
            for (int b: P)
            {
                int c = 0;
                for (int n=0; n <= 1000; n++)
                    if (P.contains(n*n – a*n – b))
                        c++;
                    else
                        break;
                if (c > maxN)
                {
                    maxA = -a;
                    maxB = -b;
                    maxN = c;
                }
            }
        }
        return String.valueOf(“A:”+maxA+” B:”+maxB+” for N:0-“+(maxN-1)+”,
so Product = “+(maxA*maxB)+”\n”);
    }

    public ArrayList<Integer> Gen (int limit)
    {
        ArrayList<Integer> p = new ArrayList<Integer>();
        p.add(1);
        int x = 2, y = 0;
        while (x < limit)
        {
            if (x % 2 != 0 || x == 2)
            {
                for (y = 2; y <= x/2; y++)
                    if (x % y == 0)
                        break;
                if (y > x/2)
                    p.add(x);
            }
            x++;
        }
        return p;
    }

}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s