(改造版)コラッツの予想：「プログラマ脳を鍛える数学パズル」Q06の答え

問題

数学の未解決問題のひとつに「コラッツの予想」があります。
自然数nについて、

・nが偶数の場合、nを2で割る
・nが奇数の場合、nに3をかけて1を足す

という操作を繰り返すとき、初期値がどんな数であっても必ず1に到達する(1→4→2→1を繰り返す)というものです。
この問題を少し変えて、初期値が偶数の場合、初回のみnに3をかけて1を足すことから始めることとし、「最初の数」に戻るものを考えます。

例えば、2で始めた場合、
2→7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2
となります。

同様に、4で始めると、 4→13→40→20→10→5→16→8→4 となります。

しかし、6で始めると、
6→19→58→29→88→44→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1→4→…
となり、6には戻ってくることはありません。

10,000以下の偶数のうち、上記の2や4のような「最初の数に戻る数」がいくつあるか、その個数を求めてください。

元ネタ：
第20回「今週のアルゴリズム：(改造版)コラッツの予想」正解者発表｜CodeIQ MAGAZINE

わたしの考え方

コラッツのルールを関数Collatz(x)として定義する。
Collatz(x)をループして繰り返し、元の数字に戻ればカウンタを1増やす。1に等しくなった場合はループをbreakする。

わたしのオリジナル解答

cnt = 0

def Collatz(x):
    if x % 2 == 0:
        x = x/2
    else:
        x = x * 3 + 1
    return x

for m in range(2, 10001, 2):
    n = m * 3 + 1
    while n != m:
        n = Collatz(n)
        if n == 1:
            break
        if n == m:
            cnt += 1
print cnt

模範解答のミソ

関数を定義して使う点は一緒だが、模範解答では最初の数に戻る場合にTrueを、1になった場合にFalseを返す関数を使っている。

修正されたわたしの解答

cnt = 0

def Collatz(x):
    y = x * 3 + 1
    while y != 1:
        if y == x:
            return True
        elif y % 2 == 0:
            y = y/2
        else:
            y = y * 3 + 1
    return False

for m in range(2, 10001, 2):
    if Collatz(m):
        cnt += 1

print cnt

気づき・反省点

range(x, y, z)とすると、3番目の引数zがstepになる。
breakはループを抜けるが、continueはループを繰り返す。breakとすべきところをずっとcontinueで書いていて、無限ループに陥ってしまっていた。
修正版のほうがコードはすっきりしたように思うが、実行速度が速くなったかどうかは分からない。