Prime-Counting Parity in Arithmetic Progressions via Sparse Hyperbola Transforms

For a nonnegative integer \(x\), this manuscript gives a deterministic fixed-multitape Turing-machine algorithm that returns the parity of the prime-counting function, \(π(x) 2\), in\[O_ε((x+2)2/5+ε)\]time and working space.More generally, let \(q≥1\), let \(S\) be a set of \(s\) prescribed invertible residue classes modulo \(q\), and put \(h=φ(q)\). Whenever \(h^3s^6≤ x\), the algorithm returns all selected values \(π(x;q,a)2\) using\[O_ε\!(h4/5s3/5x2/5(x+q+s+2)^ε)\]bit/head operations and working bits. A complementary positive squarefree transform supplies an unrestricted global envelope.The same framework computes\[∑n≤ xμ(n)^2 2ω(n) 8\]in \(x2/5+o(1)\) time. It also gives an exponent-preserving, one-oracle equivalence between prime counting modulo four and squarefree-semiprime parity. Its arithmetic-progression extension handles arbitrary selected residue classes, including zero and noninvertible classes.These results do not compute exact prime counts, the second prime-counting bit, or semiprime parity unconditionally.The accompanying Python programs perform exact finite identity and regression checks only. The Lean 4 companion contains 44 kernel-checked finite arithmetic theorems and an exhaustive reference specification. It does not formalize the fast algorithms, their asymptotic complexity, the modulus-eight theorem, or the oracle equivalence.This record contains the manuscript PDF, reproducible LaTeX source, bibliography, finite verification programs, and the limited Lean companion.