**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?

**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[10000]; 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) { answer = number; found = true; break; } number += 2; }