What Is a Goldbach-Type Problem?
Goldbach’s Conjecture states that every even integer greater than 2 can be expressed as the sum of two prime numbers. While this remains unproven in general, a rich family of Goldbach-type problems asks not whether an exact representation exists, but how close we can get when one fails — or how we can minimize error across representations.
The concrete problem we’ll solve:
Given a target integer $N$, find a pair of integers $(a, b)$ subject to constraints such that the expression $a + b$ approximates $N$, minimizing the residual $|N - (a + b)|$ under various primality and structural constraints.
More specifically, we tackle:
$$\min_{(p, q) \in \mathbb{P} \times \mathbb{P}} \left| N - (p + q) \right|$$
where $\mathbb{P}$ is the set of primes. We then extend to weighted Goldbach error:
$$E(N) = \min_{p \leq N} \left| N - p - q^* \right|, \quad q^* = \text{nearest prime to } (N - p)$$
and visualize the error landscape across a range of $N$.
The Full Source Code
1 | # ============================================================ |
Code Deep-Dive
1. sieve(limit) — NumPy Sieve of Eratosthenes
This is the engine of the entire computation. Instead of calling sympy.isprime in a loop (slow), we generate all primes up to a limit at once using a boolean array:
$$\text{is_prime}[i] = \begin{cases} \text{False} & \text{if } i < 2 \text{ or } i = k \cdot m,\ k \geq 2 \ \text{True} & \text{otherwise} \end{cases}$$
For each $i$ from 2 to $\sqrt{\text{limit}}$, we mark all multiples is_prime[i*i::i] = False. This runs in $O(n \log \log n)$ time — orders of magnitude faster than checking primality individually.
2. goldbach_error(N, primes_arr) — Core Minimizer
For each prime $p \leq N$, we want $q^*$ such that $p + q^*$ is closest to $N$:
$$q^* = \arg\min_{q \in \mathbb{P}} |N - p - q|$$
Rather than scanning all primes, we use np.searchsorted to binary-search for target = N - p in the sorted primes array — giving $O(\log k)$ per $p$ instead of $O(k)$. We then check the two neighboring elements [idx-1, idx, idx+1] to find the nearest prime. Early exit on min_err == 0.
3. weighted_goldbach_error(N, alpha, beta) — Regularized Objective
The plain error $|N - (p+q)|$ doesn’t penalize asymmetric pairs. We add a regularization term:
$$W(N; \alpha, \beta) = \alpha \cdot |N - (p + q)| + \beta \cdot \frac{|p - q|}{N}$$
The second term penalizes pairs where one prime is much larger than the other. This is analogous to L1 regularization — it encourages balanced (symmetric) decompositions. The $\beta$ parameter controls the trade-off.
4. compute_3d_surface(N_range, alpha_range) — Parameter Space Sweep
We sweep over a grid of $(N, \alpha)$ values and record $W(N, \alpha)$ at each point. This gives us a 2D error landscape that can be visualized as a 3D surface, revealing how the regularization parameter $\alpha$ interacts with the number $N$.
Performance Optimization Summary
| Technique | Speedup |
|---|---|
Sieve vs per-call isprime |
~100× for large ranges |
np.searchsorted binary search |
~50× per query over linear scan |
| Vectorized NumPy array masking | ~10× for plotting/statistics |
Early exit on error == 0 |
significant for even $N$ |
Graph-by-Graph Explanation
Plot 1 — Error by N (bar chart): The vast majority of even integers show error = 0 (green bars), consistent with Goldbach’s Conjecture holding for all tested values. Odd integers (which cannot be expressed as a sum of two primes except in trivial cases) show nonzero errors (red bars), and their magnitude reflects the local prime gap structure near $N/2$.
Plot 2 — Cumulative Error Distribution: The CDF rises steeply at 0, showing that a large fraction of all $N$ in the range achieve exact Goldbach representation. The long flat tail beyond error = 1 reveals that when errors occur, they are typically very small.
Plot 3 — Prime Pair Scatter (p, q, colored by N): Each dot represents the optimal prime pair for a given $N$. The diagonal clustering shows that pairs tend to be roughly symmetric ($p \approx q \approx N/2$), especially for larger $N$. Red × markers flag the cases where no exact solution exists.
Plot 4 — Error Magnitude Histogram: Overwhelmingly, errors are 0 or 1. This confirms the near-perfect structure: when an exact Goldbach decomposition fails, the minimum error is almost always just 1, meaning $N$ is exactly between two prime-sum values.
Plot 5 — Rolling Mean Error: The rolling window smooths out local prime gap fluctuations. The general trend is stable near zero, with slight increases where prime gaps widen (e.g., around Ramanujan primes or prime desert regions).
Plot 6 — Weighted Error vs $\alpha$ (N=97): For $N = 97$ (an odd prime), we trace how $W(97; \alpha)$ changes as we increase the weight on raw error vs symmetry penalty. There is a clear minimum — the optimal $\alpha$ that balances both objectives. This is the analog of a bias-variance trade-off in machine learning.
Plot 7 — 3D Weighted Error Surface $W(N, \alpha)$: This is the centerpiece. The surface reveals:
- Low-$\alpha$ regions where the symmetry penalty dominates
- High-$\alpha$ ridges where even $N$ maintain flat error
- Peaks corresponding to odd $N$ with large prime gaps
Plot 8 — 3D Prime Pair Landscape (p, q, N): Each 3D point $(p, q, N)$ represents the best prime pair for that $N$. Color encodes error (green = 0, red = nonzero). The diagonal sheet $p + q = N$ would be the perfect Goldbach plane — deviations from it are directly visible.
Plot 9 — Prime Gap |p−q| vs Error: Almost all exact Goldbach pairs ($\text{error}=0$) are spread across a wide range of gaps, but error > 0 cases cluster near large gaps — confirming that wide prime deserts near $N/2$ are the root cause of Goldbach failures.
Execution Results
Primes up to 500: 95 primes generated First 10: [ 2 3 5 7 11 13 17 19 23 29] Last 10: [443 449 457 461 463 467 479 487 491 499] --- Example: N = 100 --- Best pair: (3, 97) Sum: 100 Error |100 - (3+97)| = 0 Computing Goldbach errors for N in [4, 200]... Done in 0.017s Max error: 1 at N=11 Mean error: 0.2741 Fraction with error=0 (exact Goldbach): 72.6% Building 3D surface (19 x 10 grid)... 3D grid computed in 0.045s
Figure saved as 'goldbach_error_analysis.png'
Key Mathematical Takeaways
The Goldbach error $E(N)$ satisfies:
$$E(N) = 0 \iff \exists\ p, q \in \mathbb{P} : p + q = N$$
For all even $N \leq 4 \times 10^{18}$ (verified computationally), $E(N) = 0$. For odd $N$, the error is bounded by the prime gap $g(N/2)$:
$$E(N) \leq g!\left(\lfloor N/2 \rfloor\right)$$
The weighted formulation $W(N; \alpha, \beta)$ transforms this into a proper optimization problem with a tunable bias-variance trade-off — making it amenable to gradient-based or parameter-sweep methods, as demonstrated by Plot 6 and Plot 7 above.