#### Problem 46: Goldbach's Other Conjecture

9 = 7 + 2 x 1^{2}

15 = 7 + 2 x 2^{2}

21 = 3 + 2 x 3^{2}

25 = 7 + 2 x 3^{2}

27 = 19 + 2 x 2^{2}

33 = 31 + 2 x 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?

#### The Catch

How to tell when an odd composite number cannot be written as the sum of a prime and twice a square.

#### The Light

To prove Goldbach wrong, we have to find the first instance where an odd number cannot be written as the sum of a prime and twice a square. The algorithm to check whether an odd number satisfies the above condition is fairly simple: for every odd number n, start substracting prime numbers p from a list of prime numbers, one at a time (p ≤ n). If the difference is not twice a square, the corresponding number n will be the first instance to disprove Goldbach's other conjecture. In order to implement this algorithm, we need to:

- Provide a list of prime numbers. This can be done using the Sieve of Eratosthenes discussed in Problem 35.
- Check whether a quantity x is twice a square. Utilize the discussion of inverse functions in Problem 42, x is twice a square if sqrt(x/2) is an integer.

#### The Code

import java.util.*; public class Problem46 { public static void main(String[] args) { List primeList = new ArrayList(); primeList = generatePrimes(10000); for(double i = 33.0;; i += 2.0) { boolean flag = false; for(int index = 0; primeList.get(index) <= i; index++) { if(isTwiceASquare(i - primeList.get(index))) { flag = true; break; } } if(!flag) { System.out.println(i); break; } } } public static boolean isTwiceASquare(double n) { double square = Math.sqrt(n/2.0); return square == (int)square; } public static List generatePrimes(int max) { boolean[] isComposite = new boolean[max + 1]; for (int i = 2; i * i <= max; i++) { if (!isComposite [i]) for (int j = i; i * j <= max; j++) { isComposite [i*j] = true; } } ArrayList list = new ArrayList(); for (int i = 2; i <= max; i++) { if (!isComposite [i]) list.add(new Integer(i)); } return list; } }