I built a world record exact solver for the minimum line cover of prime points after watching a Numberphile video. It turned the previous 282-hour record into 22 minutes, then kept going to prove 20 new awkward primes never certified before.
After watching a Numberphile video on "awkward primes" I fell down a rabbit hole that turned into a month of obsessive C++ optimisation.
The problem: Plot the first N primes as points on a graph — the 1st prime (2) at position 1, the 2nd prime (3) at position 2, and so on. What is the minimum number of straight lines needed to pass through every point? Proving you've truly found the minimum is the hard part — it's an NP-complete set cover problem, and it gets exponentially harder as N grows.
The previous record stood at N=861, certified by Max Alekseyev (GWU) using an industrial MIP solver in 282 hours.
The solver replaces the MIP approach with an arithmetic-aware incremental architecture:
- 12,162 "heavy lines" (through 3+ primes) stored as 1024-bit bitmasks, keeping the full working set L2-resident
- 60% of steps certified instantly via witness propagation with no search at all
- Lagrangian relaxation with projected subgradient descent for tight lower bounds
- Parallel branch-and-bound with an Exclusive Dependency Rule that provably forces required lines without branching
The results: N=861 reached in 22 minutes. Full sweep to N=1024 completed in under 40 hours, certifying f(1024)=143 and finding 20 new awkward primes.
Full paper, MIT-licensed C++ source, and a live browser demo that runs the actual algorithm in real time are all at the link above. For the OEIS people: https://oeis.org/A373813