素数计数奇偶性算法复杂度大突破，5488 行 Lean 4 全靠 Claude Code
xennygrimmato_ · x · 2026-11-06
独立研究者 xennygrimmato 发布一个确定性算法，可在 x^o(1) 时间内判断不超过 x 的素数个数是奇还是偶。若 x 有 n 个比特，此前最好结果是 √x = 2^(n/2)（对 n 呈指数级），新算法为 2^(n/√log n)。
- 思路：延续 Polymath4（Tao、Croot、Helfgott）在短区间上求素数奇偶性的路线，但旧方法需要对每个 d ≤ √x 计算 Möbius 函数 μ(d)；关键洞察是 mod 2 意义下 μ(d) 只问 d 是否无平方因子——同一个问题规模减半，递归应用 log n 次后 π(x) mod 2 化为单次计数。
- 适用于任意区间 [A, B]，不限于短区间。
- 工程细节：向 Anthropic 的 #SAT 引擎发起 1 次查询；形式化证明共 5,488 行 Lean 4，用 Claude Code 写成，0 个 sorry、仅 3 条标准公理；并对 855,150 个区间做了数值验证。
所属事件:素数奇偶性判定复杂度获突破算法由Claude Code写成(4 条相关)→
「研究」频道最新
- 「10%挑战」截止收 submissions:砍掉90%权重且不许训练也要打平原模型 — tokenbender · 2026-11-13
- Photonics Atlas 收录4537个光学里程碑,按时间轴可交互浏览 — jwt0625 · 2026-11-13
- Inkling 2 Small 采纳 Kimi 注意力残差机制,作者拆解实现细节 — akbirthko · 2026-11-13
- GovAI 新论文：通用 AI 何时能自主控制军用无人机 — sethlazar · 2026-11-13
- 论文主张防御网络攻击须先教会 AI Agent 搞黑客攻击 — terryyuezhuo · 2026-11-13
- SimpleHC：去掉残差混合，仅 2.4% 额外训练时间逼近 mHC 性能 — dots-studio · 2026-11-13