Problem 046

Project Euler

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?

Here we have another problem related to prime. Since we have done so many problems with prime number, finding the prime is not an issue at this point.

From the description, we know the following:

n = p + 2 a^2 
3 \leq p < n
1 \leq a^2 \leq \frac{n-3}{2}

Notice, p can not be even or n won’t be odd.

My pseudo code algorithm is to search each odd composite number as follow starting with 9.

let n = 9
gotAnswer = false
while (!gotAnswer)
  let p = nextPrimeBelow(n)
  let found = false

  while (!found && p > 2)
    let x = (n - p) / 2
    if (isPerfectSquare(x))
      let found = true
    let p = nextPrimeBelow(p)

  if (!found)
    let answer = n
    letgotAnswer = true

  let n = nextCompositeAbove(n)

return answer

I like to return outside of a loop but you could return as soon as you found the answer. My outer while loop also only go up to one million but the answer is a lot smaller than that.

nextPrimeBelow, nextCompositeAbove and isPerfectSquare are self-explanatory. Both nextPrimeBelow and nextCompositeAbove contain another while loop that increment the search by 2 (only need odd numbers). isPerfectSquare compare the number with the square of its own rounded root.