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

15 = 7 + 2 x 2

21 = 3 + 2 x 3

25 = 7 + 2 x 3

27 = 19 + 2 x 2

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?

Related Tags:

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

`n = p + 2 x s ^{2}`

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.

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

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

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;
}
}
}
```

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))
primes.add(i);
}
return primes;
}
}
```

This problem is the 46th problem on Project Euler.

Came up with a better solution or have a question? Comment below!

Next Challenge: Index of a substring