Goldbach's Conjecture

Goldbach's Conjecture

In 1742, Christian Goldbach wrote to Euler with the following conjecture:

Every even integer greater than 2 can be expressed as the sum of two prime numbers.

For example:

• $4 = 2 + 2$
• $10 = 3 + 7 = 5 + 5$
• $28 = 5 + 23 = 11 + 17$

Despite being one of the oldest unsolved problems in mathematics, Goldbach's conjecture has been verified for all even numbers up to $4 \times 10^{18}$ — but never proved in general.

Finding a Goldbach Pair

Given an even number $n > 2$, find the pair $(p, q)$ with $p \leq q$ such that $p + q = n$ and both are prime. We want the smallest such $p$:

def goldbach_pair(n):
    primes = sieve(n)
    prime_set = set(primes)
    for p in primes:
        if n - p in prime_set and p <= n - p:
            return (p, n - p)
    return None

print(goldbach_pair(28))  # (5, 23)
print(goldbach_pair(10))  # (3, 7)

Counting Goldbach Pairs

The number of ways to write $n$ as a sum of two primes $p \leq q$ varies: some numbers have many representations. This is related to the Goldbach comet.

def goldbach_count(n):
    primes = sieve(n)
    prime_set = set(primes)
    return sum(1 for p in primes if n - p in prime_set and p <= n - p)

print(goldbach_count(28))   # 2  (5+23, 11+17)

Your Task

Using a helper sieve(n) provided in the starter code, implement:

• goldbach_pair(n) → the pair (p, q) with $p \leq q$, $p + q = n$, smallest $p$ first
• goldbach_count(n) → the number of such pairs