Pythonを使用してn個のステップを使用するcollat​​zの推測を見つける

Question

私は1になるために使用されたnステップに基づいてcollat​​zの推測を見つけることができるいくつかのPythonコードを書こうとしています。
私は少量のステップで動作するが、大量のステップが計算に時間がかかる。あなたのいずれかがこのプロセスをスピードアップする方法を知っているのであれば、私は思っていた：

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 

1は、私が探している段階の量に一致するまでこれがトラフすべての数字をループ：

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つのステップが戻ってあなたが4後12、たとえば、からはcollat​​zシーケンスを計算している後で仮定1.

にあることを見ました計算のステップ：

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

12から10にするには3つのステップが必要でした。すでに10から6ステップが必要です。これは、12から6 + 3ステップがあることをすでにわかっています。シーケンスをやり直してみる必要はありません。

また、collat​​zシーケンスを拡張しているときに12が表示された場合は、今から9つのステップがあることを思い出してください。

この情報を使ってアルゴリズムをよりスマートにするにはどうすればよいですか？