M26
Sturmian 词前缀和的快速算法：从 Fibonacci 词到一般二次无理斜率的 O(log n) 定理
来源说明：本则出自独立撰写的第二批方案。它与前 20 则同样遵循八块结构与硬门槛要求，但撰写时未做英文文献检索，新颖性边界依据的是历届获奖图谱与既有知识，而非当轮查新。因此其「需核实」条目更多，启动前须自行补一轮英文检索。
1 · 研究问题
对斜率为任意二次无理数（连分数展开最终周期）的 Sturmian 特征词，其前 n 项前缀和能否给出 O(log n) 次算术运算的精确算法，并严格证明其正确性与复杂度？当连分数周期给定时，该算法能否进一步压缩到均摊 O(1)（推广已知的 Fibonacci 词 O(1) 结果）？
2 · 研究背景与空白
Sturmian 词是复杂度最低的非最终周期无穷词，其第 k 位可写为 ⌊(k+1)α+ρ⌋−⌊kα+ρ⌋；前缀和即 ⌊nα+ρ⌋ 型和式，与三距离定理（three-distance theorem）和 Ostrowski 数系（Ostrowski numeration，基于 α 的连分数展开的整数表示）深度相关。前缀和的快速算法本质上是"数字和式的进位结构定理"，正确性与复杂度都可完全严格证明——这是纯证明型算法课题。
已有工作：丘奖 2020 铜奖《O(1) Algorithm for Calculating Prefix Sum of Fibonacci Words》解决了斜率为黄金比的特例；⌊kα⌋ 求和的经典 Euclid 型递归算法（类辗转相除，O(log n)）在竞赛编程与文献中已知（需核实其对一般 ρ 与输出字母加权的覆盖范围：搜索关键词 floor sum algorithm Sturmian Ostrowski prefix sum）；Ostrowski 数系是标准工具（Allouche–Shallit《Automatic Sequences》教材）。
空白在：把"Fibonacci 词 O(1)"结果沿连分数结构推广到一般二次无理斜率、并给出周期依赖的复杂度精确刻画，未见系统整理（第 3 周核实）。适合学生：定理链条初等（连分数 + 归纳）、每一步可机器验证、且与本赛道已获奖论文形成清晰的"推广"关系，新颖性叙事直接。
3 · 可检验假设
- H1：存在基于 Ostrowski 表示的算法，对任意固定二次无理 α 与有理 ρ，以 O(log n) 次大整数运算精确计算前缀和，并在 n ≤ 10⁷、≥ 5 个斜率上与暴力求和零偏差。
- H2：当 α 的连分数周期长 p 固定时，预处理 O(p) 后单次查询可达 O(p)（与 n 无关）,Fibonacci 词情形退化为已发表的 O(1) 结果。
4 · 量化验收标准
- 方法学校验（硬门槛）：先实现暴力前缀和与经典 Euclid 型 floor-sum 算法，两者在 n ≤ 10⁶、随机 200 组 (α 有理逼近, ρ) 上完全一致；并复现 Fibonacci 词情形已发表公式的数值输出（作为对照，不计入贡献）。不过关则全线无效。
- 新算法与暴力求和在 n ≤ 10⁷、斜率 {√2−1, √3−1, (√5−1)/2, √7−2, 黄金比平方} 上零偏差。
- 复杂度定理：给出运算次数上界的严格证明，并用实测计数曲线（运算次数 vs log n 拟合斜率，自助法 95% 置信区间）佐证。
- 退化检验：黄金比情形与 2020 铜奖论文的公式逐项一致。
- 代码开源（含验证脚本），一键复跑。
5 · 数据与工具
| 用途 | 来源 / 工具 |
|---|---|
| 大整数与连分数 | Python 内建 int + SymPy（continued_fraction_periodic），免费 |
| 暴力对照 | NumPy 逐项求和（仅校验，不计入贡献） |
| Ostrowski 数系参考 | Allouche–Shallit《Automatic Sequences》（图书馆）；公开讲义 |
| 序列对照 | OEIS（A003849 Fibonacci 词等，仅校验） |
| 算力量级 | 全部实验笔记本分钟级，纯 CPU 无压力 |
6 · 方法路径
- 实现暴力求和与经典 floor-sum 递归，完成第 4 块第 1 条校验。
- 文献窗口：核实一般斜率前缀和的已发表算法覆盖面（能力边界核实步），明确本题增量。
- 推导 Ostrowski 表示下前缀和的递推恒等式（核心引理，手工证明 + 机器验证小情形）。
- 实现 O(log n) 算法，过第 4 块第 2 条零偏差检验。
- 证明复杂度上界；对固定周期 p 推导 O(p) 查询版本，验证 Fibonacci 退化。
- 写清定理边界（哪些 ρ/字母加权已覆盖、哪些留开），整理成文。
7 · 新颖性边界
- 本课题不声称 floor-sum 型递归是新算法（竞赛编程与文献已知），不把 Fibonacci 词特例（丘奖 2020 铜奖《O(1) Algorithm for Calculating Prefix Sum of Fibonacci Words》已发表）计入贡献。
- 已有工作：Fibonacci 词 O(1) 前缀和（上述铜奖论文）；经典 ⌊kα⌋ 求和递归；Ostrowski 数系标准理论。本题差异：斜率从黄金比推广到全体二次无理数，给出周期依赖的复杂度定理与统一证明框架，并处理一般截距 ρ。
- 本项目贡献（主结论）：一般二次无理斜率的前缀和 O(log n) / 固定周期 O(p) 定理及完整证明。
- 价值：与已获奖工作构成干净的"特例 → 一般"推广关系，评委可即时定位增量；全部结论可机器复核。
8 · 决策门槛（go / no-go）
- 第 3 周末：文献核实完成。若发现一般斜率 + 一般 ρ 的同型定理已发表 → 降级路径 A：转向输出加权版本（对字母赋权 w₀, w₁ 的加权前缀和与更高阶矩，即平方和），递推框架不变；降级路径 B：转向 Sturmian 词的区间和/二维推广（billiard 词），主结论框架（Ostrowski 递推定理）保留。
- 第 8 周末：核心引理证明完成并过机器小情形验证；若递推恒等式推不出 → 先做固定周期 p = 1（√2 型）子情形，仍是超出已发表特例的定理。
- 第 20 周末：主定理与实现全部闭合，转入撰写与英文化（本题工作量前轻后重，适合与校内课业错峰）。
- 预算裁剪顺序：O(p) 查询版本 → 高阶矩扩展；O(log n) 主定理不砍。