Project Euler Solution #46: 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×1²
15 = 7 + 2×2²
21 = 3 + 2×3²
25 = 7 + 2×3²
27 = 19 + 2×2²
33 = 31 + 2×1²

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.