Prime parity algorithm details: one SAT query, 855K intervals verified numerically
xennygrimmato_ · x · 2026-11-06
The author shares key numbers for the prime-counting parity algorithm: time reduced from x^(1/2+o(1)) to x^o(1); works on any interval [A, B], not just short ones; requires a single query to Anthropic's #SAT engine; formalized in 5,488 lines of Lean 4 written with Claude Code, with 0 sorries, 3 standard axioms, and 855,150 intervals checked numerically.
Core idea: Polymath4 (Tao, Croot, Helfgott) got parity on short intervals but needed μ(d) for every d ≤ √x. Key insight: mod 2, μ(d) just asks whether d is squarefree — the same question at half the size. Applying it log n times turns π(x) mod 2 into a single count.
More from Research
- SteerAct lifts robot action-model success ~10% with just 24 rollouts per task — pliang279 · 2026-11-13
- PhD thesis explores intra-turn interaction: AI interfaces beyond turn-based dialogue — OfirPress · 2026-11-13
- CMU trains memory writing with RL: Qwen3.5-4B rivals GPT-5.4 on continual learning — aviral_kumar2 · 2026-11-13
- NTU paper: decision info lives in middle layers, last six layers removable loss-free — Minh-Anh Nguyen · 2026-11-13
- Inkling 2 Small's width-4 sconv forces a tiny rolling 3-token conv cache per layer at inference — andrew_n_carr · 2026-11-13
- Open-source legal conflict detector runs on encoder models only, 133-clause contracts in under 20s — ladyofcode · 2026-11-13