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

Question

我正在研究一些代码,当需要两个整数m和n时,需要能够有效地预测(最好在O(1)时间内)以下算法的输出.

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(当前)和n(当前)是否匹配.

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整除,直到两者相等.