A086183 研究的是:在圆周率十进制展开的前 n 位与第 n 位到第 2n-1 位之间,同时作为子串出现的最大整数。
我为这一数列编写了用于精确计算的 C++20 程序,并提交了基于后缀自动机和 suffix ranks 的复杂度分析。在编辑讨论过程中,我进一步修改了复杂度表述,明确计算模型:前 2n-1 位圆周率数字被视为输入,生成这些圆周率数字本身的成本不包含在所给出的时间和空间复杂度界中。
在这一模型下,该说明指出,a(n) 可以在 O(n) 时间和 O(n) 空间内计算;通过增量扩展后缀自动机,a(1) 到 a(N) 可以在 O(N²) 时间和 O(N) 工作内存内得到。该修改经过审核,并于 2026 年 9 月 10 日由 OEIS 编辑 Sean A. Irvine 正式发布。
精确计算
这一问题可以转化为圆周率十进制展开中两个重叠区间之间的最长公共子串类问题。后缀自动机能够紧凑地表示并完成精确的子串匹配,而 suffix ranks 则用于在满足条件的候选子串中确定数值最大的一个。
复杂度说明
在编辑讨论后,我对复杂度表述进行了修订,将“在已经给定圆周率数字的情况下进行计算”与“生成这些圆周率数字本身的成本”明确区分。若前 2n-1 位数字已经作为输入给出,则单项 a(n) 的计算复杂度为 O(n) 时间与 O(n) 空间。
增量计算
通过增量扩展后缀自动机,可以在 O(N²) 总时间和 O(N) 工作内存内计算 a(1) 到 a(N),其中同样不计入生成所需圆周率数字本身的成本。