更换OEIS序列A001511后出现List Index Out Of Range问题排查

问题背景 #

之前使用OEIS序列A000120作为s序列时，代码可正常运行并生成预期的OEIS序列A101911，但将s替换为OEIS序列A001511后，触发了List Index Out Of Range错误。尝试过调整result初始值、将r初始化为包含1的列表、修改循环范围等操作，发现给s头部添加元素时代码可正常编译，删除元素则会触发错误，需排查错误原因。

相关代码 #

import scipy.special


s = [1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3,
     1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4,
     1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3,
     1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5,
     1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3,
     1, 2, 1, 4, 1]


r = []

for n in range(20):
 result = 1
 for k in range(n-1):
     result += (scipy.special.binom(n - 1, k) % 2) * r[s[n - k - 1]]
 r.append(result)


def binomial_transform(sequence):
    n = len(sequence)
    result = [0] * n
    
    for i in range(n):
        for j in range(i+1):
            result[i] += sequence[j] * scipy.special.binom(i, j)
    
    return result

sequence = r
binomial_result = binomial_transform(sequence)
print(binomial_result)

错误原因分析 #

1. 索引访问超出r的当前长度 #

核心问题出在循环中的r[s[n - k - 1]]访问：

• r是逐步构建的，每次循环n结束后才append一个元素，因此当循环到第n次时，r的长度为n，有效索引范围是0到n-1。
• 当使用A001511作为s序列时，在某些n和k的组合下，s[n - k - 1]的值会大于等于n，导致访问r中不存在的索引，触发越界错误。
• 举个具体例子：当n=2时，k的取值范围是range(1)（即k=0），此时n - k -1 = 2-0-1=1，s[1]的值为2，但此时r只有2个元素（索引0、1），访问r[2]必然越界。而原A000120序列在s[1]的位置数值更小，不会超过r的当前长度。

2. s序列长度与循环逻辑不匹配 #

当前循环n运行20次，但s序列的数值在对应步骤中没有满足“索引值小于r当前长度”的约束。原A000120序列的数值分布刚好适配这个循环逻辑，而A001511的数值在早期步骤就出现了超出范围的情况。

3. 头部添加元素的“临时修复”原理 #

给s头部添加元素，会让n -k -1指向s中更靠前的位置，这些位置的数值更小，不会超过r当前的长度，因此暂时不会触发错误，但这只是延迟了问题——如果循环次数足够多，最终还是会出现索引越界。

解决方向 #

• 检查A001511序列的数值，确保在循环的每个步骤中，s[n -k -1]的值小于当前r的长度（即小于n）。
• 调整循环逻辑，比如先初始化r包含足够的初始元素，或者根据s的数值动态调整r的生成顺序，保证访问索引时对应的元素已经存在。

内容的提问来源于stack exchange，提问作者John Smith