# Project Euler Problem 46: Goldbach's other conjecture

Question:

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

9 = 7 + 2 x 12
15 = 7 + 2 x 22
21 = 3 + 2 x 32
25 = 7 + 2 x 32
27 = 19 + 2 x 22

It turns out the conjecture was false. What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

## Writing out the math

Before we break this down into components, let's try rearranging the conjecture.

n = p + 2 x s2

Where n is the number, p is our prime number, and s is the value we need to square.

We then rearrange this equation to obtain the following:

s = sqrt((n-p)/2)

Since s must be an integer, the right hand side of the equation must equate to a whole number. If not, the conjecture does not hold for those values of n and p.

Furthermore, we note how n < p since we can't take the square root of a negative number.

## Algorithm Pseudocode

1. Given a value n, obtain a list of all primes less than n.
2. For each prime p in our list, we take sqrt( (n - p) / 2 ).
3. If the result is an integer, (no decimal places) then the conjecture holds, and we can move on to the next odd n.
4. If not, move onto the next prime value, p.
5. If we have exhausted our prime values list, then we found the value of which the conjecture does not hold.

## Obtaining a list of all primes < our number

To obtain a list of values less than some n, we can apply the Sieve of Eratosthenes.

## Implementation in Java

Here's the implementation. The findPrimes() method returns an ArrayList of primes less than a given input.

This method returns the value 5777.

static int disproveGoldbach() {

// Start at 1
int currentNum = 1;

// Our list of prime arrays
ArrayList<Integer> listOfPrimes;

// Boolean to exit loop when all done
boolean done = false;

// Keep running until we find a value that doesn't work
while (true) {

// Get list of prime numbers for the current number
listOfPrimes = findPrimes(currentNum);

// Try out all options in our list of prime numbers
for (int j = 0; j < listOfPrimes.size(); j++) {

int currentPrime = listOfPrimes.get(j);

double eval = Math.sqrt((currentNum - currentPrime) / 2) % 1;

// If there exists an int we can square and double
if (eval == 0.0) {
break;
}

// If we've exhausted our list, and no solutions are found, return!
if (j == listOfPrimes.size() - 1) {
return currentNum;
}
}

// only odd numbers
currentNum += 2;

}
}
}

## Full runnable code

Here's the full, runnable code in case you want to test it out yourself.

import java.lang.Math;
import java.util.HashMap;
import java.util.ArrayList;

public class Goldbach {

public static void main(String[] args) {

System.out.println(disproveGoldbach());

}

static int disproveGoldbach() {

// Start at 1
int currentNum = 1;

// Our list of prime arrays
ArrayList<Integer> listOfPrimes;

// Boolean to exit loop when all done
boolean done = false;

// Keep running until we find a value that doesn't work
while (true) {

// Get list of prime numbers for the current number
listOfPrimes = findPrimes(currentNum);

// Try out all options in our list of prime numbers
for (int j = 0; j < listOfPrimes.size(); j++) {

int currentPrime = listOfPrimes.get(j);

double eval = Math.sqrt((currentNum - currentPrime) / 2) % 1;

// If there exists an int we can square and double
if (eval == 0.0) {
break;
}

// If we've exhausted our list, and no solutions are found, return!
if (j == listOfPrimes.size() - 1) {
return currentNum;
}
}

// only odd numbers
currentNum += 2;

}
}

static ArrayList<Integer> findPrimes(int n) {

// A key prime Integer will have a Boolean value of true.
HashMap<Integer, Boolean> primeTable = new HashMap<>();

// Load our table with values up to and including n.
for (int i = 1; i <= n; i++) {
primeTable.put(i, true);
}

// 1 is by definition not prime.
primeTable.put(1, false);

// For every value up to the sqrt(n).
for (int i = 2; i * i < n; i++) {
// If particular value is still set as prime
// (otherwise those values will have already been covered.
if (primeTable.get(i)) {

// Set each multiple as not a prime
for (int p = i+i; p <= n; p += i) {
primeTable.put(p, false);
}
}
}

// Now store all primes into a list and return
ArrayList<Integer> primes = new ArrayList<>();

for (int i = 1; i <= primeTable.size(); i++) {
if (primeTable.get(i))
}