🔢 mathematics

GoldbachGPU: An Open Source GPU-Accelerated Framework for Verification of Goldbach's Conjecture

GoldbachGPU is an open-source, segmented GPU framework that overcomes previous memory limitations to exhaustively verify Goldbach's conjecture up to 10^12 on a single consumer GPU and extend arbitrary-precision verification to 10^10000, while demonstrating clean scalability across multi-GPU data-center hardware.

Original authors: Isaac Llorente-Saguer

Published 2026-03-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Isaac Llorente-Saguer

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive puzzle. The puzzle is Goldbach's Conjecture, a math problem that has been around since 1742. The rule is simple: Every even number bigger than 2 can be made by adding two prime numbers together.

For example:

4 = 2 + 2
10 = 3 + 7
100 = 3 + 97

Mathematicians have checked this for trillions of numbers, but they haven't proven it for every single number in existence. This paper introduces a new tool called GoldbachGPU that checks these numbers incredibly fast using a standard computer graphics card (the kind gamers use).

Here is how the paper works, explained with everyday analogies:

1. The Old Problem: The "Filing Cabinet" Bottleneck

Imagine you are a librarian trying to find if a specific book exists. In the past, computer scientists tried to put a list of every single prime number (the "books") into the computer's super-fast memory (VRAM) to check them instantly.

The Issue: The list of prime numbers is huge. As the numbers get bigger, the list gets so long that it doesn't fit in the computer's memory. It's like trying to stuff an entire library's worth of books into a single backpack.
The Limit: Previous attempts hit a "wall" around 100 billion ( $10^{11}$ ). Once the list got too big for the backpack, the computer had to stop.

2. The Solution: The "Smart Segmentation" Strategy

The author, Isaac Llorente-Saguer, didn't try to force the whole library into the backpack. Instead, he invented a two-step strategy that changes how the computer looks for the answer.

Step A: The "Bit-Packed" Suitcase

First, he realized the old way of storing numbers was wasteful. It was like storing every book in a giant, empty cardboard box.

The Fix: He compressed the data. Instead of a box for every book, he used a tiny, dense suitcase where 16 books fit in the space of one. This 16x compression meant the computer could hold a much longer list of primes in its memory without overflowing.

Step B: The "Segmented" Assembly Line (The Big Breakthrough)

Even with the smaller suitcase, the list was still too long for the biggest numbers (up to 1 trillion, or $10^{12}$ ). So, he changed the workflow entirely.

Imagine you are checking a long line of people (even numbers) to see if they have a matching partner (a prime number).

The Old Way: You grab the entire list of potential partners, bring them all to the line, and check every person against everyone else. This requires a massive room (memory).
The GoldbachGPU Way: You only bring a small group of partners to the line at a time.
1. You check the first group of people.
2. If you find a match, you move to the next group.
3. If you don't find a match with the small group, you have a "safety net" (a rigorous CPU check) that does a deep, slow search to make sure you didn't miss anything.

The Magic: Because you only need to hold a tiny "segment" of the partner list in memory at any one time, the computer never runs out of space. It's like a factory assembly line where you only keep the tools for the current task on the table, rather than the tools for the whole factory.

3. The "Oracle" (The Three-Step Detective)

To make this fast, the computer uses a "three-tiered detective" system to check if a number is prime:

The Quick Look: Is the number very small? Check a tiny, permanent list in the computer's brain (L2 Cache). Instant answer.
The Current Segment: Is the number in the current small group we are working on? Check the list currently on the table (VRAM). Very fast answer.
The Deep Dive: Is the number in the "in-between" zone? Run a complex math test (Miller-Rabin) to be sure. Slower, but necessary.

This system ensures the computer spends 99% of its time on the "Quick Look" and "Current Segment," which are super fast.

4. The Results: Breaking the Record

Using a standard gaming graphics card (an NVIDIA RTX 3070, which costs a few hundred dollars), this new framework:

Checked every even number up to 1 Trillion ( $10^{12}$ ).
Found zero counterexamples. (Every single number checked still followed the rule).
Took about 41 minutes to do what used to take days or required massive supercomputers.
Used almost no memory (only 14 MB per segment), meaning it could theoretically go even higher if needed.

They also built a special tool to check individual, gigantic numbers (up to 10,000 digits long), verifying them in seconds.

5. Why This Matters

It's Open Source: Anyone can download the code, run it on their own computer, and verify the results.
It's Accessible: You don't need a million-dollar supercomputer. A standard gaming PC can now do world-class mathematical verification.
It's Efficient: It proved that the previous "memory wall" wasn't a law of physics; it was just a bad design. By changing the design, we can go much further.

In a nutshell: The author took a problem that was stuck because computers ran out of "desk space," and solved it by teaching the computer to work in small, manageable shifts, using a super-efficient filing system. The result? We can now check the rules of the universe (math) up to a trillion, right from a home computer.

1. Problem Statement

Goldbach's Conjecture posits that every even integer greater than 2 is the sum of two prime numbers. While theoretically unproven, it has been computationally verified up to $4 \times 10^{18}$ using distributed CPU clusters. However, verification on commodity hardware (specifically single consumer GPUs) has been severely limited by VRAM (Video RAM) constraints.

Prior GPU-based approaches relied on storing a monolithic prime table in VRAM. This created a "hard memory ceiling" near $10^{11}$ , as storing a byte-per-number representation for larger ranges exceeded the 8–24 GB VRAM available on consumer cards. Consequently, no existing open-source framework had demonstrated exhaustive verification beyond $10^{11}$ on a single GPU.

2. Methodology

The authors propose GoldbachGPU, a framework comprising five complementary tools that scale from CPU baselines to arbitrary-precision verification. The core innovation lies in the Segmented Double-Sieve Verifier (goldbach_gpu3).

Key Architectural Components:

Dense Bit-Packed Representation:
Instead of storing primes as bytes, the framework uses a 64-bit word array where each bit represents an odd integer. This achieves a 16× reduction in memory footprint compared to byte-array storage, allowing a prime table up to $10^{11}$ to fit within 8 GB of VRAM (5.96 GB).
Segmented Double-Sieve Architecture:
To overcome the $10^{11}$ limit, the framework abandons the monolithic table. It adopts a segmented approach inspired by Oliveira e Silva's loop inversion strategy:
1. Loop Inversion: Instead of iterating through even numbers $n$ and searching for primes $p$ , the system iterates through candidate primes $p$ and marks valid partitions for even numbers $n$ .
2. Segmented Processing: The range is divided into segments (e.g., $10^7$ even integers). For each segment, the CPU generates a small prime bitset (approx. 14 MB) and transfers it to the GPU.
3. Three-Way Primality Oracle: For a given even number $n$ $n$ in the current segment and a candidate prime $p$ $p$ , the system checks if $q = n - p$ $q = n - p$ is prime using a priority chain:
  - Priority 1: $q \le P_{SMALL}$ ( $10^6$ ): Lookup in a permanently resident small-primes bitset (~122 KB).
  - Priority 2: $q \in [A, B]$ (current segment): Lookup in the current 14 MB segment bitset.
  - Priority 3: $P_{SMALL} < q < A$ : Deterministic 64-bit Miller–Rabin test.
    This design ensures $O(1)$ VRAM usage regardless of the total range $N$ , as only the current segment resides in memory.
Fallback and Verification Chains:
- CPU Fallback: If Phase 1 (GPU) fails to find a partition for any $n$ , a rigorous CPU exhaustive search is triggered. In all experiments, this was never invoked.
- Arbitrary Precision (big_check): Uses GMP and OpenMP with a synchronized batch-search strategy to verify individual numbers up to $10^{10,000}$ digits, preventing thread runaway in parallel execution.

3. Key Contributions

Elimination of the VRAM Ceiling: The segmented double-sieve design removes the memory barrier, enabling exhaustive verification up to $10^{12}$ on a single consumer GPU (NVIDIA RTX 3070, 8 GB VRAM).
Memory Efficiency: A dense bitset representation reduces memory requirements by 16×, enabling GPU-resident tables up to $10^{11}$ .
Correctness Guarantee: A two-phase design (GPU fast-path + CPU fallback) ensures mathematical completeness without relying on unproven bounds for the minimal Goldbach prime.
Scalability: The framework demonstrates clean multi-GPU scaling on data-center hardware (tested on 8× H100) and supports arbitrary-precision verification up to $10^{10,000}$ .
Open Source: The entire codebase is open-source, documented, and reproducible on both consumer and high-end hardware.

4. Results

Verification Range: The framework successfully verified all even integers up to $10^{12}$ on a single RTX 3070 in approximately 41 minutes. No counterexamples were found.
Performance:
- Speedup: At $10^9$ , the GPU implementation achieved a 16× speedup over the CPU baseline.
- Scaling: Runtime scales linearly ( $O(N)$ ) with the range. The segmented design maintains constant per-segment cost.
- Multi-GPU: Strong scaling on 6× RTX 3090 GPUs showed near-linear efficiency (91% at 4 GPUs, 80% at 6 GPUs).
Empirical Validation of Minimal Prime Bounds: The 100% success rate of Phase 1 (GPU-only) across the entire $10^{12}$ range empirically confirms that the minimal Goldbach prime $p_{min}(n) \le 2 \times 10^6$ for all even $n \le 10^{12}$ . This aligns with theoretical predictions ( $H(10^{12}) \approx 2000$ ).
Arbitrary Precision: Verified a 10,001-digit number ( $10^{10,000}$ ) in 182 seconds using 20 threads.

5. Significance and Limitations

Significance:
This work proves that the limitations of prior GPU Goldbach verification were architectural (monolithic memory allocation) rather than fundamental. By inverting the verification loop and utilizing segmented sieving, GoldbachGPU democratizes high-range verification, allowing a single consumer card to outperform previous single-GPU efforts by an order of magnitude. It bridges the gap between commodity hardware and the massive distributed clusters previously required for such tasks.

Limitations & Future Work:

CPU Bottleneck: The current implementation is limited by the CPU-based segmented sieve construction, which must generate prime tables before GPU transfer. On high-end hardware (H100), the GPU often idles waiting for the CPU.
Algorithmic Gap: The current approach performs per- $n$ primality lookups. The authors identify that adopting a bitwise bulk-marking kernel (similar to the full double-sieve method) could reduce complexity to $O(N \log \log N)$ and eliminate Miller–Rabin fallbacks, potentially pushing verification to $10^{15}$ on a single GPU.
Memory Bandwidth: Performance is sensitive to host memory bandwidth; large segments can starve high-bandwidth GPUs if the host CPU cannot feed data fast enough.

In conclusion, GoldbachGPU represents a significant leap in computational number theory, providing a scalable, open, and rigorous framework for verifying Goldbach's Conjecture on widely accessible hardware.