# Project Euler 46: Finding a counterexample to a Goldbach conjecture

I'm working on problem 46 from project euler:

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?

My code is so ridiculously inefficient and it takes minutes before an answer pops up. (Boundary numbers are just rough estimates)

numbers = [(2*x**2) for x in list(range(1, 1000))]
normal = list(range(1, 10000000))

#produces primes under n
def primes(n):
sieve = [True] * n
for i in range(3, int(n**0.5) + 1, 2):
if sieve[i]:
sieve[i * i:: 2 * i] = [False] * int((n - i * i - 1)/(2 * i) + 1)
return  + [i for i in range(3, n, 2) if sieve[i]]

primes = primes(1000)
final = []

#add the two lists in every way possible
added = [x + y for x in numbers for y in primes]

#if it does not appear in a normal number line send it to final
if x not in normal:
final.append(x)

print(min(final))


I also lack the knowledge to use any mathematical tricks or algorithms. Where can I start learning code efficiency/performance and simple algorithms to use in my code?

• One thing to keep in mind is that normal python isn't the fastest language around. Would implementing this in something like C++ be an option? – yuri Jun 30 '17 at 12:22
• Yes, how would I do that and how much faster would it be? – Po Chen Liu Jun 30 '17 at 12:26
• The increase in performance differs based on what you are doing. Here is a comparison of various python and C++ programs to give you an idea. – yuri Jun 30 '17 at 12:43

# Optimization

It seems that you have tried to optimize your code using the sieve of Eratosthenes; however, the sieve of Eratosthenes is only useful if there is a given upper bound in the problem statement.

An optimal solution can be achieved for this problem via brute-force in the following manner (pseudocode):

n = ... # the smallest odd composite number

loop forever:
solution_found = False
for all possible x:
possible_prime = n - 2 * x ** 2
if is_prime(possible_prime):
solution_found = True
break
if not solution_found:

Note that the above is merely pseudocode. For the line for all possible x, it is possible to bound x. Also (and most importantly), the is_prime() method needs to be cleverly thought out, possibly caching values.
• So, you need to solve n = p + 2x^2. One possible way (there are others) is to write the equation as p = n - 2x^2. Now, try plugging in x = 0, 1, 2, ... until p is prime. We can stop searching for x when p becomes negative, hence the highest x possible causes n - 2x^2 = 0. Then, solving for x gives x = sqrt(n/2). So if there is no x in the range 0 to sqrt(n/2) satisfying the previously mentioned equation, then there is no solution, meaning n is the answer. – ljeabmreosn Jul 1 '17 at 3:23
• @jschnei The sieve of Eratosthenes is useful when the numbers in are in some range. But suppose we need to determine if n is prime. Okay, run the sieve. Then, determine if n^2 + 2 is prime. You would then need to rebuild the table which is very inefficient. The trial division algorithm is O(sqrt(n)), Omega(1) whereas the sieve is Theta(nloglogn). It would be nice if you could point me to the dynamic sieve implementation you mentioned! – ljeabmreosn Jul 3 '17 at 1:04