Prime-counting parity in x^o(1) time, with 5,488 lines of Lean 4 written by Claude Code
xennygrimmato_ · x · 2026-11-06
Researcher xennygrimmato released a deterministic algorithm that decides whether the number of primes up to x is odd or even in x^o(1) time. For n-bit x, the previous best was √x = 2^(n/2) (exponential in n); the new algorithm runs in 2^(n/√log n).
- Idea: extends Polymath4's (Tao, Croot, Helfgott) short-interval parity approach, which needed μ(d) for every d ≤ √x. Key insight: mod 2, μ(d) only asks whether d is squarefree — the same question at half the size. Applying this log n times reduces π(x) mod 2 to a single count.
- Works for any interval [A, B], not just short ones.
- Engineering: 1 query to Anthropic's #SAT engine; a 5,488-line Lean 4 formalization written with Claude Code, with 0 sorries and 3 standard axioms; 855,150 intervals verified numerically.
More from Research
- Dejan's LLM brand study probes 193k brand mentions for just $391.71 using Gemini — dejanseo · 2026-11-13
- Galaxea Co-founder Hang Zhao's CoRL Keynote: Split Robot Intelligence into System 2/1/0 by Timescale — YuXiang_IRVL · 2026-11-13
- A Summary of the Macy Conferences: The Birthplace of Cybernetics and Early AI Thought — ArtificialOther · 2026-11-13
- vismatch: unified API wrapping 50+ image matching models, 943 stars on GitHub — gabriberton · 2026-11-13
- Stanford's Speculative Self-Distillation cuts training tokens 38-69% with less forgetting — khademinori · 2026-11-13
- EEPO: Adaptive Sample-Then-Forget Rollouts Break Diversity Collapse in RLVR Training — burkov · 2026-11-13