# Project Euler

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

Here we have another problem related to prime. Since we have done so many problems with prime number, finding the prime is not an issue at this point.

From the description, we know the following:

$n = p + 2 a^2$
$3 \leq p < n$
$1 \leq a^2 \leq \frac{n-3}{2}$


Notice, p can not be even or n won’t be odd.

My pseudo code algorithm is to search each odd composite number as follow starting with 9.

let n = 9
let p = nextPrimeBelow(n)
let found = false

while (!found && p > 2)
let x = (n - p) / 2
if (isPerfectSquare(x))
let found = true
let p = nextPrimeBelow(p)

if (!found)
return answer