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.

<!-- TEASER_END -->


```python
from IPython.display import Math, display

from collections import defaultdict
from itertools import count
```

We modify and augment a very space-efficient implementation (due to David Eppstein, UC Irvine) of the Sieve of Erastothenes to generate *composite* numbers and keep track of all prime numbers below it. In the outermost-loop below, `primes` will always be the list of all prime number strictly below $n$, i.e. it is equivalent to $P_n$. Note that if $n$ is odd and composite, then the largest prime below it is no greater than $n-2$, since $n-1$ is even. Since $\max S_n = n - 2$ searching through $P_n$ is sufficient (i.e. if $n-2$ is prime, then $n-2 \in P_n$.) The loop terminates when we encounter an $n$ with no witnesses.


```python
factors = defaultdict(list)
witness = {}
primes = set()
for n in count(2):
    if factors[n]:
        # n is composite
        for m in factors.pop(n):
            factors[n+m].append(m)
        if n % 2:
            # n is odd and composite
            for k in range(1, int((n/2)**.5)+1):
                p = n - 2*k**2
                if p in primes: 
                    # TODO: `in` is O(len(primes))
                    # could optimize by using set
                    witness[n] = k
                    break
            if not n in witness:
                break
    else:
        factors[n*n].append(n)
        primes.add(n)
```


```python
n
```




    5777



The answer is 5777.

Note that not only is this implementation space-efficient, it is also very time efficient, since we incrementally build our list of primes, composites and witnesses incrementally from bottom-up. If we hadn't augmented the implementation of the prime sieve, we would have had to use the prime sieve to obtain all odd composites, and perform a primality test on all elements of $S_n$, which would (usually) require a prime factorization algorithm, which in turn (usually) requires a prime sieve, not to mention the fact that there would be many overlapping subproblems, i.e. many $n < m$ such that $S_n \cap S_m \ne \emptyset$, so we'd have to use dynamic programming, by, for example memoizing the primality testing function or some other optimization - just a whole mess of redundancies and inefficiencies that we happily avoided with this method :)

Let's list out the witnesses to the first 100 numbers.


```python
lines = [r'{0} &= {1} + 2 \cdot {2}^2 \\'.format(n, n - 2*witness[n]**2, witness[n]) for n in sorted(witness)]
```


```python
Math(r"""
     \begin{{align}}
     {body}
     \end{{align}}
     """.format(body='\n'.join(lines[:100])))
```




$$
     \begin{align}
     9 &= 7 + 2 \cdot 1^2 \\
15 &= 13 + 2 \cdot 1^2 \\
21 &= 19 + 2 \cdot 1^2 \\
25 &= 23 + 2 \cdot 1^2 \\
27 &= 19 + 2 \cdot 2^2 \\
33 &= 31 + 2 \cdot 1^2 \\
35 &= 17 + 2 \cdot 3^2 \\
39 &= 37 + 2 \cdot 1^2 \\
45 &= 43 + 2 \cdot 1^2 \\
49 &= 47 + 2 \cdot 1^2 \\
51 &= 43 + 2 \cdot 2^2 \\
55 &= 53 + 2 \cdot 1^2 \\
57 &= 7 + 2 \cdot 5^2 \\
63 &= 61 + 2 \cdot 1^2 \\
65 &= 47 + 2 \cdot 3^2 \\
69 &= 67 + 2 \cdot 1^2 \\
75 &= 73 + 2 \cdot 1^2 \\
77 &= 59 + 2 \cdot 3^2 \\
81 &= 79 + 2 \cdot 1^2 \\
85 &= 83 + 2 \cdot 1^2 \\
87 &= 79 + 2 \cdot 2^2 \\
91 &= 89 + 2 \cdot 1^2 \\
93 &= 61 + 2 \cdot 4^2 \\
95 &= 23 + 2 \cdot 6^2 \\
99 &= 97 + 2 \cdot 1^2 \\
105 &= 103 + 2 \cdot 1^2 \\
111 &= 109 + 2 \cdot 1^2 \\
115 &= 113 + 2 \cdot 1^2 \\
117 &= 109 + 2 \cdot 2^2 \\
119 &= 101 + 2 \cdot 3^2 \\
121 &= 113 + 2 \cdot 2^2 \\
123 &= 73 + 2 \cdot 5^2 \\
125 &= 107 + 2 \cdot 3^2 \\
129 &= 127 + 2 \cdot 1^2 \\
133 &= 131 + 2 \cdot 1^2 \\
135 &= 127 + 2 \cdot 2^2 \\
141 &= 139 + 2 \cdot 1^2 \\
143 &= 71 + 2 \cdot 6^2 \\
145 &= 137 + 2 \cdot 2^2 \\
147 &= 139 + 2 \cdot 2^2 \\
153 &= 151 + 2 \cdot 1^2 \\
155 &= 137 + 2 \cdot 3^2 \\
159 &= 157 + 2 \cdot 1^2 \\
161 &= 89 + 2 \cdot 6^2 \\
165 &= 163 + 2 \cdot 1^2 \\
169 &= 167 + 2 \cdot 1^2 \\
171 &= 163 + 2 \cdot 2^2 \\
175 &= 173 + 2 \cdot 1^2 \\
177 &= 127 + 2 \cdot 5^2 \\
183 &= 181 + 2 \cdot 1^2 \\
185 &= 167 + 2 \cdot 3^2 \\
187 &= 179 + 2 \cdot 2^2 \\
189 &= 181 + 2 \cdot 2^2 \\
195 &= 193 + 2 \cdot 1^2 \\
201 &= 199 + 2 \cdot 1^2 \\
203 &= 131 + 2 \cdot 6^2 \\
205 &= 197 + 2 \cdot 2^2 \\
207 &= 199 + 2 \cdot 2^2 \\
209 &= 191 + 2 \cdot 3^2 \\
213 &= 211 + 2 \cdot 1^2 \\
215 &= 197 + 2 \cdot 3^2 \\
217 &= 199 + 2 \cdot 3^2 \\
219 &= 211 + 2 \cdot 2^2 \\
221 &= 149 + 2 \cdot 6^2 \\
225 &= 223 + 2 \cdot 1^2 \\
231 &= 229 + 2 \cdot 1^2 \\
235 &= 233 + 2 \cdot 1^2 \\
237 &= 229 + 2 \cdot 2^2 \\
243 &= 241 + 2 \cdot 1^2 \\
245 &= 227 + 2 \cdot 3^2 \\
247 &= 239 + 2 \cdot 2^2 \\
249 &= 241 + 2 \cdot 2^2 \\
253 &= 251 + 2 \cdot 1^2 \\
255 &= 223 + 2 \cdot 4^2 \\
259 &= 257 + 2 \cdot 1^2 \\
261 &= 229 + 2 \cdot 4^2 \\
265 &= 263 + 2 \cdot 1^2 \\
267 &= 139 + 2 \cdot 8^2 \\
273 &= 271 + 2 \cdot 1^2 \\
275 &= 257 + 2 \cdot 3^2 \\
279 &= 277 + 2 \cdot 1^2 \\
285 &= 283 + 2 \cdot 1^2 \\
287 &= 269 + 2 \cdot 3^2 \\
289 &= 281 + 2 \cdot 2^2 \\
291 &= 283 + 2 \cdot 2^2 \\
295 &= 293 + 2 \cdot 1^2 \\
297 &= 199 + 2 \cdot 7^2 \\
299 &= 281 + 2 \cdot 3^2 \\
301 &= 293 + 2 \cdot 2^2 \\
303 &= 271 + 2 \cdot 4^2 \\
305 &= 233 + 2 \cdot 6^2 \\
309 &= 307 + 2 \cdot 1^2 \\
315 &= 313 + 2 \cdot 1^2 \\
319 &= 317 + 2 \cdot 1^2 \\
321 &= 313 + 2 \cdot 2^2 \\
323 &= 251 + 2 \cdot 6^2 \\
325 &= 317 + 2 \cdot 2^2 \\
327 &= 277 + 2 \cdot 5^2 \\
329 &= 311 + 2 \cdot 3^2 \\
333 &= 331 + 2 \cdot 1^2 \\
     \end{align}
     $$



81bf8d93e9ee9b5542204c7435c3380f761cb629
ipynb
Jupyter Notebook
problem-46-goldbachs-other-conjecture.ipynb
ltiao/project-euler
94a5705f09c69271142b1d2ca5581a988cbc0e3c
Unlicense
problem-46-goldbachs-other-conjecture.ipynb
ltiao/project-euler
94a5705f09c69271142b1d2ca5581a988cbc0e3c
Unlicense
problem-46-goldbachs-other-conjecture.ipynb
ltiao/project-euler
94a5705f09c69271142b1d2ca5581a988cbc0e3c
Unlicense
Qwen/Qwen-72B
1. YES
2. YES