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

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

« Back to problem overview