如何检查序列是否循环或重复

Question

我有一个程序可以生成 3n + 1 问题的数字。程序取n的值并迭代直到n变为1。

n = 49

number = n
current_iter = 0 
computed_nums = [n] 
iterations = [0]
while n != 1:
    if n % 2 == 0:
        n = (n / 2)
    else:
        n = ((n * 3) + 1)
    current_iter += 1
    computed_nums.append(n)
    iterations.append(current_iter)

print("Computed numbers: " + str(computed_nums))
print("Iterations required: " + str(current_iter))

如何检查序列是否循环或重复？

Answer 1

您只需要跟踪您已经访问过的号码并检查 n 是否是其中之一。

n = 49

computed_nums = {}
while n not in computed_nums:
    if n % 2 == 0:
        res = n // 2
    else:
        res = n*3 + 1
    computed_nums[n] = res
    n = res  # For next loop

print(list(computed_nums))
print("Iterations:", len(computed_nums)-1)

输出：

[49, 148, 74, 37, 112, 56, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
Iterations: 24

这里我使用了一个字典，它保留了 Python 3.7 的插入顺序。

注意：Collatz 猜想已经测试了 2⁶⁸，所以检查 n == 1 在实践中是否足够。

如何检查序列是否循环或重复

How to check if sequence cycles or repeats

python

collatz