CODEWITHSUNDEEP
pythonprimesgoldbach-conjecture
Denis Mclaughlin
Denis Mclaughlin

Reputation: 63

Checking Goldbach's conjecture holds up to N

I've been asked to write a piece of code that checks that Goldbach's conjecture holds for every even number up to N, so far I have the following:

def gb(n):
    #give a list of all primes less than n using the sieve of Eratosthenes (not considering 1 to be prime like Goldbach):
    primes=list(range(2,n+1))

    for i in primes:

        j=2

        while i*j<=primes[-1]:
            if i*j in primes :
                primes.remove(i*j)
                j=j+1

    #give a list of even numbers less than n but starting from 4
    evens=list(range(4,n+1,2))

I then need to check if all the numbers in evens can be made as the sum of two numbers in primes. I'm confused at this point, I know that I need to use loops but I'm not sure as to how to check if all of them fit the conjecture?

Upvotes: 2

Views: 1225

Answers (3)

Andy Richter
Andy Richter

Reputation: 189

Here. This keeps the gist of your original idea. The sieve code I just found on the web.

def sieve(x): 
   isprime = [False,True]*(x//2+1)
   isprime[1] = False
   isprime[2] = True
   for i in range(3, x+1, 2):
      if isprime[i]:
         for j in range(i*i, x, 2*i):
            isprime[j] = False
   return [i for i,v in enumerate(isprime) if v] 
    
def gb(n):
   ans = []
   #give a list of all primes less than n using the sieve of Eratosthenes (not considering 1 to be prime like Goldbach):
   primes = sieve(n)
   for i in primes:
      if i > n//2: break # avoids (3,7) and (7,3)
      if n-i in primes:
         ans += [(i,n-i)] 
   return ans
   
n = 200
#give a list of even numbers less than n but starting from 4
evens=list(range(4,n+1,2))
for i in evens:
    print(f"{i} {gb(i)}")

Upvotes: 0

tobias_k
tobias_k

Reputation: 82929

Instead of looping over all the even numbers, and for each checking whether there is a combination of two primes that sums to that number, you can do the inverse: Collect all the sums of two primes in a set (fast lookup in O(1)) and for each even number check whether it is in that set.

>>> N = 1000
>>> primes = [p for p in range(N+1) if not any(p % q == 0 for q in range(2, p//2))]
>>> evens = [n for n in range(4, N+1, 2)]
>>> sums = set(p + q for p in primes for q in primes)
>>> all(n in sums for n in evens)
True

Of course, primes can be implemented more efficiently using the sieve, but that's not really relevant here. Given primes, checking the numbers would have complexity of O(P^2 + N), with P being the number of primes smaller than N.

Alternatively, if you do not want to calculate and store the sums for all the P^2 combinations of two primes, you could turn the primes into a set and for each even number n, find a prime p such that n - p is also in primes. This would have complexity O(N * P), but needs less space

>>> primes = set(primes)
>>> all(any(n - p in primes for p in primes) for n in evens)

Upvotes: 1

inspectorG4dget
inspectorG4dget

Reputation: 114025

This should do it:

import itertools
import math

def check(n, primes):
    """Check if Goldbach's conjecture holds for n, given a list of primes"""

    for a,b in itertools.product((p for p in primes if p<n), repeat=2):
        if a+b == n: return True
    return False


def checkAll(N):
    """Check whether Goldbach's conjecture holds for all even numbers >2, <=N"""

    primes = getPrimes(N)
    for n in range(4, N+1):
        if not check(n, primes): return False
    return True


def checkPrime(n, primes):
    """Check whether n is prime, given a list of prime numbers smaller than it"""
    for p in primes:
        if p > math.ceil(n**0.5): return True
        if not n%p: return False
    return True


def getPrimes(N):
    """Get all prime numbers <=N"""
    answer = [2,3]
    for n in range(5, N+1):
        if check(n): answer.append(n)

Upvotes: 0

Related Questions