# Project Euler Problem 46: Goldbach's other conjecture

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 \cdot 1^2 \\ 15 = 7 + 2 \cdot 2^2 \\ 21 = 3 + 2 \cdot 3^2 \\ 25 = 7 + 2 \cdot 3^2 \\ 27 = 19 + 2 \cdot 2^2 \\ 33 = 31 + 2 \cdot 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?

#### Version 1: Brute force¶

Formally stated, Goldbach's Other Conjecture says that all odd composite numbers $n$ can be expressed as

$$ n = 2k^2 + p $$

for some integer $k$ and prime number $p$. Let

$$ S_n = \{ n - 2k^2 : k = 1, 2, \dotsc, \lfloor \sqrt{\frac{n}{2}} \rfloor \} $$

If any element $n - 2k^2$ of $S_n$ is prime, then we call $k$ a *witness* to Goldbach's Other Conjecture for $n$. We are asked to find the smallest $n$ that has no witness, i.e. such that *all* elements of $S_n$ are composite.

Let $P_n$ be the set of all prime numbers stricly smaller than $n$, then our algorithm searches for the smallest $n$ such that $P_n \cap S_n = \emptyset$, providing a counterexample to Goldbach's Other Conjecture.