Hacker News Reader

Comment by SethTro | Hacker News Reader

> 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?

View on HN

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.

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.

Reply on news.ycombinator.com