Checking Goldbach's conjecture holds up to N

Question

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?

tobias_k · Answer 1 · 2016-12-07T22:28:02.070

1

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)

edited Dec 07 '16 at 22:28

answered Dec 07 '16 at 21:52

tobias_k

81,265
12
120
179

as you use it, there is no need for `evens` to be a list at all or to build it that way, a simple `list(range(...))` is sorter (or just range in py2), being a range object is more that enough and more memory friendly if you are in python 3 (xrange in py2) – Copperfield Dec 08 '16 at 00:21
a range object is NOT a generator, we usually use as such, but is not... you can iterate over the same range as many time as you like, and it implement the Sequence ABC, so you can do membership testing and get its elements by index, its size, and etc... – Copperfield Dec 08 '16 at 17:13
@Copperfield You are right, I forgot. So, yes, you could just as well use `range` directly, without the list comprehension or without even converting it to a list. – tobias_k Dec 08 '16 at 18:18
@tobias_k, sorry as this is an old answer, but is there an elegant way to only add p+q to the 'sums' set if the result is even? I was thinking this might be a way to save on memory space? – TNoms Aug 05 '21 at 10:20
1

@TophNoms All primes except 2 are odd, so `p + q` will _always_ be even unless either `p` or `q` (but not both) is `2`, so you could just pop the `2` from the `primes` and add the `4` to the `sums` set manually. – tobias_k Aug 05 '21 at 13:15
@tobias_k of course, that was silly of me. The issue I am facing is that I'm trying to figure out how many times each even number can be split into two primes (e.g. 10 can be made from 7,3 and 5,5, so twice), but doing this for every even number up to 1 million requires a lot of memory. – TNoms Aug 05 '21 at 13:32
@TophNoms You could try the last approach in my answer, just replace `any` with `sum`; or create a `dict` / `defaultdict` / `Counter`, iterate all combinations of two primes below a million (there are ~78000) and increment the count for their sum. Doing all those combination takes some time (O(P^2), P being number of primes), but only O(N) memory (N being number of (even) numbers) – tobias_k Aug 05 '21 at 15:35

score 0 · Answer 2 · answered Dec 07 '16 at 21:40

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)

Checking Goldbach's conjecture holds up to N

2 Answers2