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×1^{2}

15 = 7 + 2×2^{2}

21 = 3 + 2×3^{2}

25 = 7 + 2×3^{2}

27 = 19 + 2×2^{2}

33 = 31 + 2×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?

## Solution

Goldbachs Other Conjecture states that all odd composite numbers \(n\) can be expressed as

\[n = p + 2k^2\]

with \(p\) being a prime and \(k\in\mathbb{Z}\). When we create a set of witnesses \(W_n\) until \(n\) for Goldbachs conjecture

\[W_n = \left\{ n - 2k^2 | k = 1, 2,3, \dots, \left\lfloor\sqrt\frac{n}{2}\right\rfloor \right\}\]

in theory, all we have to do is finding the smallest \(n\) such that \(P_n \cap W_n\neq \emptyset\) as a counter-example for the conjecture, with \(P_n\) being the set of primes smaller than \(n\).

To find an efficient solution for this problem, we start with \(n=9\) as the smallest odd composite number and check that all primes \(p\in P_n\) can be used to make \(\frac{n-p}{2}=k^2\) square:

```
for n = 9; ; n+= 2
for p in P_n
if (n - p) / 2 is square
break
else
return n
```

The for-else-statement here is by analogy to Pythons statement, where else is executed after the loop ended normally, without a break. We could also reverse this idea and walk through all double square numbers and check if there is a witness for number \(p = n - 2k^2\) to be prime:

```
for n = 9; ; n+= 2
if n is prime
continue
for k = 1; 2 * k * k < n; k++
if n - 2 * k * k is prime
else
return n
```

Practically, the second approach has the advantage of a complexity of \(O(n\sqrt{n})\) if the prime check were constant. This would be the case if we had a pre-computed prime table, but since all prime checks are less than \(n\), we can create the prime table on the go with the Sieve of Eratosthenes:

```
function solution(limit) {
const sieve = new Uint8Array(limit + 1);
sieve[0] = 1;
sieve[1] = 1;
for (let n = 2; n <= limit; n++) {
if (sieve[n] === 0) { // is prime?
for (let k = n * n; k <= limit; k+= n) {
sieve[k] = 1;
}
} else if (n % 2 === 1) { // is odd composite
let hasWitness = false;
for (let k = 1; 2 * k * k < n; k++) {
if (sieve[n - 2 * k * k] === 0) {
hasWitness = true;
break;
}
}
if (!hasWitness) return n;
}
}
return null;
}
```

To speed up the implementation, we can copy the prime canceling out for all multiples of two, so that we step through all odd numbers only afterwards:

```
function solution(limit) {
const sieve = new Uint8Array(limit + 1);
sieve[0] = 1;
sieve[1] = 1;
// Mark every multiple of two
for (let k = 2; k <= limit; k+= 2) {
sieve[k] = 1;
}
for (let n = 3; n <= limit; n+= 2) {
if (sieve[n] === 0) { // is odd prime?
for (let k = n * n; k <= limit; k+= n) {
sieve[k] = 1;
}
} else { // is odd composite
let hasWitness = false;
for (let k = 1; 2 * k * k < n; k++) {
if (sieve[n - 2 * k * k] === 0) {
hasWitness = true;
break;
}
}
if (!hasWitness) return n;
}
}
return null;
}
```

Interestingly, with series A060003, OEIS lists all odd numbers that are not of the form \(p+2k^2\), which is pretty small and believed to be finite. This list also contains our composite number for this problem.

Goldbach was a funny guy, generating conjectures that others must prove wrong but solving such problems gives much insight into the nature of numbers.