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 [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?
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!