Project Euler 46: Finding a counterexample to a Goldbach conjecture

Question

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 + ×ばつ1^2 
15 = 7 + ×ばつ2^2
21 = 3 + ×ばつ3^2
25 = 7 + ×ばつ3^2
27 = 19 + ×ばつ2^2
33 = 31 + ×ばつ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 [2] + [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 
for x in added:
 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?

• yuri: 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?
• Po Chen Liu: Yes, how would I do that and how much faster would it be?
• yuri: 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.

Answer 1

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:
 print("Answer: " + n)
 break
 n = n + ... # what to increment by? 

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.

Note: I just tested my implementation based on the above pseudocode and got the answer instantaneously. Too bad Goldbach didn't have a computer!

• ljeabmreosn: 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.
• jschnei: It's not at all true that "the sieve of Eratosthenes is only useful if there is a given upper bound". Sieving is useful whenever you want to test primality of a large number of numbers in a (relatively) small range. If you don't know the exact range of the numbers, that isn't an obstacle in and of itself; you can always use a strategy where you double the size of the range and recompute each time you need a larger range (similar to how dynamic arrays are allocated). This will be asymptotically faster.
• jschnei: Also I think you should be very careful when calling solutions "optimal" unless you can actually prove they are optimal. (There are faster solutions for this problem, especially if you're willing to trade some time for memory).
• ljeabmreosn: @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!
• jschnei: I can't find an implementation that does exactly what I described, but there is a similar algorithm that goes by names like "segmented sieve" which works via similar principles (e.g. primesieve.org/segmented_sieve.html). The important thing to realize is that you definitely don't have to rebuild the table every time you want to do a new check. You only ever have to extend the table. Of course, if you extend it by a factor of 2 each time, it doesn't matter asymptotically if you just rebuild the whole table instead (and you'll do at most log(max) rebuilds).