AtCoder ABC 116 B – Collatz Problem Python解説

2021年12月6日

Collatz Problem

今回の問題は「Collatz Problem」。コラッツの問題は未解決問題のひとつで、nが偶数の場合nを2で割り、nが奇数の場合nに3を掛けて1を足すことを繰り返すと、どうなるのかという問題です。

この問題では初項sが与えられ、先述したように、nが偶数の場合nを2で割り、nが奇数の場合nに3を掛けて1を足していった結果、最初に要素の重複が起こるのは第何項なのかを求めていきます。

s = int(input())

a = []
i = 1

while True:
    if s not in a:
        a.append(s)
        i += 1
        if s % 2 == 0:
            s //= 2
        else:
            s = 3 * s + 1
    else:
        print(i)
        break
    

要素の重複が起こるまで続くのでwhile文で書きました。要素が配列aになければ要素を追加し、次の要素は偶数か奇数かを見て計算を変えています。要素の重複が起きたら重複が起きた項数を出力して完了です。