Trillion-Scale Goldbach Verification on Consumer Hardware -Novel Algorithm [pdf]

Posted3 months agoActive3 months ago

josh_kratz

7 points

9 comments

zenodo.orgResearchstory

calmpositive

Debate

20/100

Number TheoryAlgorithm DesignComputational Mathematics

Key topics

Number Theory

Algorithm Design

Computational Mathematics

Researchers present a novel algorithm for verifying Goldbach's conjecture on a trillion-scale, achievable on consumer hardware, sparking discussion on its implications and potential applications.

Snapshot generated from the HN discussion

Discussion Activity

Light discussion

First comment

N/A

Peak period

5-6h

Avg / period

1.5

Key moments

01Story posted
Oct 9, 2025 at 8:03 PM EDT
3 months ago
Step 01
02First comment
Oct 9, 2025 at 8:03 PM EDT
0s after posting
Step 02
03Peak activity
2 comments in 5-6h
Hottest window of the conversation
Step 03
04Latest activity
Oct 10, 2025 at 5:12 AM EDT
3 months ago
Step 04

Generating AI Summary...

Analyzing up to 500 comments to identify key contributors and discussion patterns

Discussion (9 comments)

Showing 9 comments

josh_kratzAuthor

3 months ago

2 replies

Author here. This is my first published paper - developed independently. Novel approach uses a fixed set of witness primes to reduce verification to O(1) per even. Full C# implementation on GitHub for anyone to run.

SethTro

3 months ago

1 reply

> Goldbach states: every even number ≥ 4 is a sum of two primes. The naive check for an even n tries many primes p and hopes that n − p is prime. Our idea is simpler: fix a small set of primes Q = {q1, . . . , qK} (the “gear”), and for each even n only test p = n − q with q ∈ Q

I don't see how your idea is different from the naive check. As far as I can tell you are basically saying do the naive check but only up to p > 250-300?

josh_kratzAuthor

3 months ago

1 reply

The idea is that a fixed gear approach means that instead of exhaustively checking against everything, a small subset of primes (k=300) actually is sufficient for effectively complete coverage and holds true at large slices in the quadrillions, or even higher, or all the way through an entire cycle of evens to 1 trillion. It’s saving a massive amount of compute and appears to be just as effective as naive checks. Like orders of magnitude faster.

As far as I know, no one has tested this method or written an algorithm precisely like this. And then determined that k=300 is the sweet spot for primes sets. Complexity isn’t required for improvements.

josh_kratzAuthor

3 months ago

Think of it like this: “naive 300“ would try and check if n minus any of the first 300 primes lands on another prime. For big n, it falls apart fast as prime gaps explode, and you start missing left and right. But here I am doing a small, constant set of primes, call it the “gear”… and for each even n, I check n – q for every q in that gear. Not just as a casual test, but as a full-blown, multi-threaded, checkpointed sweep with audited logs.

SethTro

3 months ago

1 reply

I don't see any benchmarks on your github.

How long does it take for you to test up to 10^9? 10^12?

josh_kratzAuthor

3 months ago

1 reply

So at 12 threads. I can do 10^12 in about 3hrs and 45 mins. But obviously takes over the whole system. I think it could even be more optimized if the concept was taken further in the right hands or hardware. I should add some benchmarks for sure. Will do so soon.

SethTro

3 months ago

Is that for [0, 10^12] or for 10^18 + 10^12? Is the 3.75 hrs total core hours or system time?

I wrote https://github.com/sethtroisi/goldbach in the last four hours and I think it's 10-100x faster than your code

  time ./goldbach -t8 -K 1024 -e 100''000''000''000
  real 0m44.133s
  user 3m32.193s
  sys 0m0.092s

  time ./goldbach -t12 -K 1500 -e 1''000''000''000''000
    267468893942 = 267468891139 + 2803 (407)
    926868341768 = 926868338701 + 3067 (437)
    599533546358 = 599533542901 + 3457 (481)
  real 2m3.909s
  user 16m0.729s
  sys 0m37.960s

I know of at least another 4x I could improve it but I've been nerd sniped enough for the night.

I wouldn't trust it 100% but it finds all terms in https://oeis.org/A025018 and https://oeis.org/A025019 and I can verify in https://sweet.ua.pt/tos/goldbach.html

YoshiRulz

3 months ago

1 reply

The repo (it looks like ~500 LOC of C# in a single file with no deps, cool): https://github.com/joshkartz/Fixed-Gear-Goldbach-Engine

josh_kratzAuthor

3 months ago

Yep, that’s the one. Nothing crazy. It might get angry at certain versions of .NET though.

View full discussion on Hacker News

ID: 45534270Type: storyLast synced: 11/17/2025, 11:12:54 AM

Want the full context?

Jump to the original sources

Read the primary article or dive into the live Hacker News thread when you're ready.

Open link View on HN