Python程序优化：提升tes效率及判断LCM是否属于{3^d}

1. 提升tes处理效率 #

• 替换精度不可靠的对数判断：原代码用浮点对数判断是否为3的幂，存在精度误差，改为数学验证法：不断将LCM除以3，直到无法整除，若最终结果为1则是3的幂。
• 提前终止无意义计算：由于shifts中每个元素都是偶数，LCM必然包含因子2，而3的幂（d≥1时）均为奇数，因此直接可得出结论：不存在满足条件的N、M，无需遍历到tes=700即可终止程序。

2. 利用对称性消除冗余计算 #

LCM(shifts(n,m))=LCM(shifts(m,n))，因此只需遍历N ≤ M的组合，将循环范围从O(tes²)缩减为O(tes²/2)，直接减少一半计算量。

3. 用列表推导式优化shifts列表定义 #

通过数学推导将原while循环生成shifts的逻辑转为列表推导式，避免循环中的变量修改，提升生成效率：

s = min(N, M)
shifts = []
if s >= 2:
    t = (s - 2) // 2 + 1
    shifts = [2*(N + M - 4*k) - 4 for k in range(t)]

该推导式等价于原循环的逻辑，直接生成所有shifts元素。

4. 数学层面证明LCM与{3^d}无交集 #

从解析角度分析：

• shifts中每个元素可表示为2*(N+M-2-4k)（k为非负整数），均为偶数，因此LCM(shifts)必然包含质因子2。
• 集合{3^d}中的元素：d=0时为1（被lcm>1的条件排除），d≥1时均为奇数，不含质因子2。
• 因此不存在任何N、M使得LCM(shifts(N,M))属于{3^d}，无需进行数值计算即可得出结论。

优化后的代码 #

import math

tes = 700

def is_power_of_three(num):
    if num <= 1:
        return False
    while num % 3 == 0:
        num = num // 3
    return num == 1

# 利用对称性，只遍历N ≤ M的组合
for N in range(tes + 1):
    for M in range(N, tes + 1):
        s = min(N, M)
        shifts = []
        if s >= 2:
            t = (s - 2) // 2 + 1
            shifts = [2*(N + M - 4*k) - 4 for k in range(t)]
        
        # 计算LCM
        lcm = 1
        for num in shifts:
            lcm = lcm * num // math.gcd(lcm, num)
        
        if is_power_of_three(lcm):
            print(shifts, N, M, lcm)

注：由于数学上已证明无满足条件的情况，此代码不会输出任何结果，可直接终止循环以节省资源。

相关技术资源 #

• 数论参考：初等数论教材中“等差数列的最小公倍数”章节，重点关注公差与首项的互质关系对LCM的影响。
• Python性能优化：使用标准库math.gcd替代自定义实现（标准库为C扩展，速度更快），利用列表推导式替代显式while循环减少开销。

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