コラッツの問題

Longest Collatz sequenceを解いたので、忘備録

pythonによる回数計算

collatz.py

def collatz(n, c = 1):
    if n == 1 : 
        return c
    else:
        c += 1
        return collatz(n // 2, c) if n % 2 == 0 else collatz(3 * n + 1, c)

10からスタートすると
10　→　5　→　16　→　8　→　4　→　2　→　1
と変化して、１になるまでの回数を計算する関数collaz

collatz(10)の結果は、7となる。
再帰を使っている割には動きはよくて、あとで１００００００回くりかえしてもなんとか動いた。

１０００００までのうち一番多い回数を調べる。

単純にやってみる

bruteforce.py

def collatz(n, c = 1):
    if n == 1 : 
        return c
    else:
        c += 1
        return collatz(n // 2, c) if n % 2 == 0 else collatz(3 * n + 1, c)


def longest_collatz(n):
    i = 1
    l = []
    while i <= n:
        l.append(collatz(i))
        i += 1
    return (max(l), l.index(max(l))+1)

print(longest_collats(1000000))

ボーとして待っていると、回答がタプルで返ってくる。
pythonってすごいな。

工夫してみる。

use_dict.py

def l_collatz(n):
    d = {}
    colz=lambda x: x // 2 if x % 2 == 0 else 3 * x +1
    d[1] = 1
    for i in range(1,n + 1):
        k = 0  # 回数を初期化
        c = i
        while c not in d:  #　すでに数字がでていない場合
            k += 1
            c = colz(c)
        d[i] = k + d[c]  # 以前出てきた数字がきた場合、回数を足して終了
    return sorted(d.items(), key=lambda x:x[1])[-1]
    #  値で降順ソートして一番最初を返してる
print(l_collatz(1000000))

lambdaや辞書を使って、いったん出てきた数字を辞書に格納してスピードアップしたもの

結構見やすく書けた

もっと工夫してみる

use_dict_list.py

def ll_collatz(n):
    d = {1:1}
    for i in range(1, n + 1):
        k = 0
        c = i
        l = []
        while c not in d:
            l.append(c)
            k += 1
            c = c // 2 if c % 2 == 0 else 3 * c + 1
        for idx,v in enumerate(l):
            d[v] = k - idx + d[c]

    return max(d, key=d.get)

print(ll_collatz(10000000))

いったん出てきた数字はすべて辞書にしてみた
速度はあまり変わらなかった・・・・
奇数の時にできる数が多くて、効率が悪くなっているような気がする。

まとめ

再帰とか、辞書をなんとか使えるようになってきたのがいい感じです。