python - 使用python找到使用n步得到一个的collat​​z猜想

Question

所以我正在尝试编写一些 python 代码，让我根据用于达到 1 的 n 个步骤找到 collat​​z 猜想。
我有一些可以用少量的步骤工作，但是大量的步骤需要很长时间才能计算出来。所以我想知道你们中是否有人知道加快此过程的方法:

def cj(i):

out = []
out.append(i)
while i != 1:
    if i%2==0:
        i = i/2
        out.append(i)
    else:
        i = i*3+1
        out.append(i)
return out

循环遍历所有数字，直到一个数字与我正在寻找的步数相匹配:

def cj_steps(n):
x = 1
while True:
    if len(cj(x))-1 ==  n:
        return x
    else:
        x +=1

正如我所说，这需要少量的步骤，但以 812 步为例，这已经开始需要很多时间了。所以我希望有人能给我一些提示或提示，告诉我如何提高这个功能的速度。

谢谢。

Answer 1

这是给你的一个想法。假设您从 10 计算 collat​​z 序列:

>>> collatz(10)
[10, 5, 16, 8, 4, 2, 1]

你看到有 6 步回到 1。

假设稍后您正在计算从 12 开始的 collat​​z 序列。经过四步计算后:

>>> collatz(12)
[12, 6, 3, 10, ...

等一下!!从 12 到 10 需要 3 步。我们已经知道从 10 需要 6 步。所以这已经告诉我们从 12 开始有 6+3 步，而不需要费心再次计算序列。

此外，如果我们在扩展 collat​​z 序列时再次看到 12，请记住我们现在距离统一有 9 步。

您如何使用这些信息使您的算法更智能？