Euler Problem 46

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 2×1^(2)
15 = 7 + 2×2^(2)
21 = 3 + 2×3^(2)
25 = 7 + 2×3^(2)
27 = 19 + 2×2^(2)
33 = 31 + 2×1^(2)

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

Not too tricky. Need to notice that the prime number and the number squared are always less than the composite.

import java.util.*;

public class Euler46
{
    public static void main(String[] args)
    {
        Euler46 e = new Euler46();
        System.out.format(“Problem: %s\n”, e.getClass().getName());
        System.out.format(“Answer = %s\n”, e.Problem());
    }
    public String Problem ()
    {
        ArrayList<Integer> C = new ArrayList<Integer>();
        ArrayList<Integer> P = new ArrayList<Integer>();
        ArrayList<Integer> T = new ArrayList<Integer>();
        int n = 10000;
        boolean [] isPrime = new boolean [n+1];
        for (int i = 2; i < n; i++)
            isPrime[i] = true;
        for (int p = 2; p*p < n; p++)
            if (isPrime[p] == true)
                for (int m = p*p; m < n; m = m+p)
                    if (m % p == 0)
                        isPrime[m] = false;
        for (int i = 2; i < n; i++)
            if (isPrime[i])
                P.add(i);
            else
                if (i % 2 != 0)
                    C.add(i);
        boolean flag = true;
        for (int i = 0; i <= C.size()-1; i++)
        {
            flag = true;
            A: for (int p = 0; P.get(p) < C.get(i); p++)
                for (int m = 1; m < Math.sqrt(C.get(i)); m++)
                    if ((P.get(p) + 2*m*m) == C.get(i))
                    {
                        flag = false;
                        System.out.format(“%d: %d + 2*%d^2\n”, C.get(i), P.get(p), m);
                        break A;
                    }
            if (flag)
                T.add(C.get(i));
        }
        return String.valueOf(T.get(0));
    }
}

According to Wiki, every integer greater than one is either a prime number or a composite number.



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