B - Collatz Problem 解説

問題

考え方

nとaiは関数f(n)の項数となっている。
従ってn にaiを代入していく。

iが2、3、4、、、の時はai = f(ai -1)となる。
つまり、

i = 1の時　a1 = 8
i = 2の時　a2 = f(a1) = f(8) = 4 
i = 3の時　a3 = f(a2) = f(4) = 2 
i = 4の時　a4 = f(a3) = f(2) = 1 
i = 5の時　a5 = f(a4) = f(1) = 4 

となり、初項sがどんな値であれ4→2→1が繰り返される。

mは項数であり、

nよりも大きいmかつ、最小の項数を求める。

am = an （ m > n ）、つまり最初に要素の重複が起こる項数を答えとすればよい。

要素の重複が起こる項数を求めるという発想に辿り着けなかった。

答え

s = int(input())

a = []
i = 1

while True:
    if s not in a: ##初稿が配列aにない間.sは8,4,2,1,4と繰り返し、4が出たので1に4をたした５が出力される。
        a.append(s)
        i += 1
        if s % 2 == 0:
            s //= 2
        else:
            s = 3 * s + 1
    else:
        print(i)
        break

参考