python - 有效地预测数字处理算法的输出

Question

我正在编写一些代码，需要能够有效地预测(最好在 O(1) 时间内)以下算法在出现两个整数 m 和 n 时的输出。

algorithm(m,n):
history = set()
while True:
    if (m,n) in history:
        return False
    elif n == m:
        return True
    else:
        history.add((m,n))
        if m>n:
            x = m-n
            y = 2*n
            m = x
            n = y
        else:
            x = 2*m
            y = n-m
            m = x
            n = y

请注意，当 (m,n) 出现在以下算法的历史记录中时，您已进入无限循环(即 2,1 -> 1,2 -> 2,1...)；当 m==n 时，算法只能向前推进一步并且必须终止(即 5,5 -> 10,0 -> 10,0...)。本质上，我需要能够预测 m(current) 和 n(current) 是否会匹配。

PS，如果这个算法有名字我很想知道。此外，如果有关于这个主题的好读物(预测数字序列等...)，我很乐意被引导到它。

Answer 1

假设输入正整数，当且仅当 (m+n)/gcd(m, n) 是 2 的幂时，该算法才会返回 True。

证明草图:

在算法开始时将 m 和 n 除以 gcd(m, n)；这不会改变返回值。

如果执行此操作后 m 和 n 的和可以被奇素数 p 整除，则 m 和 n 都需要被 p 整除才能使算法返回 True，但 m 和 n 都不能这样做。

如果 m 和 n 的总和是 2 的幂，则每次迭代时 m 和 n 都可以被另一个 2 整除，直到两者相等。