New deterministic algorithm decides parity of prime counting function in x^o(1) time
xennygrimmato_ · x · 2026-11-06
A new deterministic algorithm decides whether the number of primes up to x is odd or even in x^o(1) time — for n-bit x, down from the previous best of √x = 2^(n/2) (exponential in n) to 2^(n/√log n). Key insight: building on Polymath4 (Tao, Croot, Helfgott), which needed μ(d) for every d ≤ √x, the author notes that mod 2 μ(d) just asks whether d is squarefree — the same question at half the size. Applied log n times, π(x) mod 2 reduces to a single count. Paper released.
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