# 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());
}
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])
else
if (i % 2 != 0)
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)