如何用Python优化Collatz序列计算？减少检查次数求最长序列起始项

问题背景 #

我是Python基础学习者，需要找到小于100的数中生成最长Collatz序列的起始项，同时希望尽可能减少检查的数字数量。Collatz序列规则：

• 若n为奇数：n = 3n + 1
• 若n为偶数：n = n/2
  注：偶数和5的倍数都可能是答案（比如小于20时答案是18）。原代码会遍历1-100所有数字，正确答案是97。

原代码问题 #

原代码存在两个明显问题：

1. 函数Collatz直接引用外部循环变量i，会导致NameError（函数参数未传入i）；
2. 遍历所有数字且无缓存，重复计算大量序列项，效率低下。

优化方案：记忆化缓存减少重复计算 #

核心思路是用缓存字典存储已经计算过的数字的序列长度，当计算某个数的序列时，遇到已缓存的数直接复用结果，无需重复迭代，大幅减少计算量。

优化后代码 #

# 缓存已计算的Collatz序列长度，初始值：1的序列长度为0（无需迭代到终点）
collatz_cache = {1: 0}

def get_collatz_length(n):
    if n in collatz_cache:
        return collatz_cache[n]
    # 根据Collatz规则计算下一项的长度，再加当前步的1次迭代
    if n % 2 == 0:
        length = 1 + get_collatz_length(n // 2)
    else:
        length = 1 + get_collatz_length(3 * n + 1)
    # 将当前数的长度存入缓存，供后续复用
    collatz_cache[n] = length
    return length

max_length = 0
max_num = 0

# 遍历1到99，查找最长序列的起始项
for num in range(1, 100):
    current_length = get_collatz_length(num)
    if current_length > max_length:
        max_length = current_length
        max_num = num

print(f"生成最长Collatz序列的起始项是：{max_num}，序列长度为：{max_length}")

优化说明 #

1. 缓存机制：比如计算97的序列时，中间遇到的数字（如292、146等）会被存入缓存，后续其他数字的序列如果遇到这些数，直接调用缓存结果，无需重复计算；
2. 逻辑解耦：函数只负责计算单个数字的序列长度，主循环负责遍历和比较，代码结构更清晰；
3. 效率提升：即使遍历1-99，实际需要完整计算的数字远少于99个，对于更大范围的数，缓存的优势会更明显。

进一步减少检查数量的思路 #

如果想进一步减少遍历的数字，可以利用Collatz序列的性质：

• 若数字m是数字n序列中的项，那么n的序列长度必然比m长（因为n要先走到m再继续迭代），因此我们只需检查那些不在任何更小数字序列中的数。不过对于100以内的范围，缓存方案已经足够简单高效，适合基础学习者理解和实现。

内容的提问来源于stack exchange，提问作者Luca Krishnan