Problem 939: Goldbach Partition Counting

Mathematical Foundation

Definition. For even $n \geq 4$, the Goldbach partition function is:

Theorem 1 (Goldbach’s conjecture — computational verification). Every even integer $n$ with $4 \leq n \leq 4 \times 10^{18}$ satisfies $G(n) \geq 1$.

Proof. This has been verified computationally (Oliveira e Silva, 2013, verified up to $4 \times 10^{18}$). For our range $n \leq 10^6$, the verification is trivial by direct computation. $\square$

Theorem 2 (Sieve-based computation of $G(n)$). Let $\mathcal{P}$ denote the set of primes. Then:

Proof. Each unordered pair $\{p, q\}$ with $p + q = n$ and $p \leq q$ corresponds uniquely to a prime $p \leq n/2$ such that $q = n - p$ is also prime. The constraint $p \leq q$ is equivalent to $p \leq n/2$. $\square$

Lemma 1 (Counting identity). The total $\sum_{\substack{n=4 \\ n \text{ even}}}^{N} G(n)$ counts the number of unordered pairs of primes $(p, q)$ with $p \leq q$ and $p + q \leq N$ even. Equivalently, it counts all pairs of primes summing to an even number at most $N$, with $p \leq q$.

Proof. Each pair $(p, q)$ with $p \leq q$ both prime and $p + q = n$ even is counted exactly once in $G(n)$. Summing over all even $n$ from 4 to $N$ collects all such pairs. Note that $p + q$ is even iff both are odd or both equal 2; since 2 is the only even prime, the only pair with $p = q = 2$ gives $n = 4$, and all other pairs have $p = 2$ (giving odd $q = n - 2$, so $n$ is even) or both $p, q$ odd (giving even sum). $\square$

Theorem 3 (Hardy—Littlewood conjecture, asymptotic). For even $n \to \infty$:

where $C_2 = \prod_{p > 2}\left(1 - \frac{1}{(p-1)^2}\right) \approx 0.6602$ is the twin prime constant.

Proof. This is a heuristic conjecture based on the Hardy—Littlewood circle method. A rigorous proof remains open. The formula gives excellent empirical agreement for large $n$. $\square$

Editorial

Optimized approach:*. We sieve of Eratosthenes up to N. We then iterate over each even n, count G(n) and accumulate. Finally, iterate over n from 4 to N step 2.

Pseudocode

Sieve of Eratosthenes up to N
For each even n, count G(n) and accumulate
for n from 4 to N step 2
for p from 2 to n/2
Sieve primes
For each prime p, count even n in [2p, N] such that n - p is prime
Equivalently: for each pair (p, q) with p <= q, p + q <= N, p + q even

Complexity Analysis

• Time (naive): $O\!\left(\sum_{\substack{n=4 \\ n \text{ even}}}^{N} \frac{n}{2}\right) = O(N^2)$.
• Time (optimized): $O(\pi(N/2)^2) \approx O\!\left(\frac{N^2}{\ln^2 N}\right)$, which is a constant-factor improvement.
• Time (sieve): $O(N \log \log N)$ for the Eratosthenes sieve.
• Space: $O(N)$ for the primality array.

Answer

#include <bits/stdc++.h>
using namespace std;
int main(){
    const int N=100000;
    vector<bool> sieve(N+1,true);
    sieve[0]=sieve[1]=false;
    for(int i=2;i*i<=N;i++) if(sieve[i]) for(int j=i*i;j<=N;j+=i) sieve[j]=false;
    long long total=0;
    for(int n=4;n<=N;n+=2){
        int cnt=0;
        for(int p=2;p<=n/2;p++) if(sieve[p]&&sieve[n-p]) cnt++;
        total+=cnt;
    }
    cout<<total<<endl;
    return 0;
}

"""
Problem 939: Goldbach Partition Counting

Compute the sum of G(n) for all even n in [4, N], where G(n) is the number
of ways to write n = p + q with p <= q and both prime (Goldbach partitions).

Key observations:
    - G(4) = 1 (2+2), G(6) = 1 (3+3), G(8) = 1 (3+5), G(10) = 2 (3+7, 5+5)
    - G(n) tends to grow roughly like n / (2 * ln(n)^2) for large n
    - The sum of G(n) counts total Goldbach representations up to N

Results:
    - Sum of G(n) for even n up to 10000 computed below

Methods:
    1. sieve_of_eratosthenes  -- generate prime flags up to N
    2. goldbach_count         -- G(n) for a single even n
    3. sum_goldbach           -- sum of G(n) for even n in [4, N]
    4. goldbach_ratio         -- G(n) vs n/ln(n)^2 heuristic
"""
import numpy as np

def sieve_of_eratosthenes(N):
    """Return boolean list where sieve[i] = True iff i is prime."""
    sieve = [True] * (N + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(N**0.5) + 1):
        if sieve[i]:
            for j in range(i * i, N + 1, i):
                sieve[j] = False
    return sieve

def goldbach_count(n, sieve):
    """G(n) = number of pairs (p, q) with p <= q, p+q = n, both prime."""
    count = 0
    for p in range(2, n // 2 + 1):
        if sieve[p] and sieve[n - p]:
            count += 1
    return count

def sum_goldbach(N):
    """Compute sum of G(n) for all even n from 4 to N."""
    sieve = sieve_of_eratosthenes(N)
    total = 0
    g_vals = []
    for n in range(4, N + 1, 2):
        g = goldbach_count(n, sieve)
        g_vals.append(g)
        total += g
    return total, g_vals, sieve

def goldbach_ratio(n, g_n):
    """Ratio G(n) / (n / ln(n)^2) -- Hardy-Littlewood estimate."""
    if n <= 2 or g_n == 0:
        return 0.0
    ln_n = np.log(n)
    return g_n / (n / (ln_n ** 2))

# Verification
sieve_small = sieve_of_eratosthenes(100)
assert goldbach_count(4, sieve_small) == 1    # 2+2
assert goldbach_count(6, sieve_small) == 1    # 3+3
assert goldbach_count(8, sieve_small) == 1    # 3+5
assert goldbach_count(10, sieve_small) == 2   # 3+7, 5+5
assert goldbach_count(20, sieve_small) == 2   # 3+17, 7+13

# Computation
N = 10000
answer, g_vals, sieve = sum_goldbach(N)
print(answer)