# Project Euler 46 Solution: 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×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.