# Project Euler: Problem 46 – Goldbach’s other conjecture

#### 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×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12

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?

#### Idea:

First, I had to look up what “odd composite” meant (in short: odd, non-prime number). From there, I made a list of the first 10000 prime numbers and I started with 3 and looped through every odd number to see if it was prime. If it wasn’t, I looped through the list of prime numbers and applied the formula above until I found and odd composite that couldn’t be written as the sum of a prime and twice a square.

```int answer = -1;

int[] primes = new int;
BigInteger base = BigInteger.ONE;
for(int i = 0; i < primes.length; i++) {
base = base.nextProbablePrime();
primes[i] = base.intValue();
}

boolean found = false;
int number = 3;
while(!found) {
//test odd composite for prime-ness
if(BigInteger.valueOf((long)number).isProbablePrime(10)) {
number += 2;
continue;
}
boolean cantBeWritten = true;
for(int i = 0; primes[i] < number && cantBeWritten; i++) {
int tmp = number-primes[i];
tmp = tmp / 2;
int result = (int)Math.sqrt(tmp);
if(result*result*2 + primes[i] == number) {
cantBeWritten = false;
}
}
if(cantBeWritten) {