使用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开始的折叠序列.经过四个计算步骤:

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

坚持一分钟!!从12到10需要3个步骤.我们已经知道从10开始,需要6个步骤.因此,我们已经告诉我们,从12开始有6 + 3步,而无需再费心去计算序列.

此外,如果我们在扩展一个连枷序列时再次看到12,可以记住我们现在距离团结9步.

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