コラッツ・角谷の問題 in Python DouKaku?

任意の数nを与えたときに
・nが偶数ならば2で割る　(n=n/2)
・nが奇数ならば3倍して1を足す （n = 3*n+1)
を繰り返すと、いづれは1になる。というものがあります。

数値計算の上ではかなりの数まで成り立つことが知られています。
（すべての数について成り立つかは不明）
参考リンク先参照

ある任意の数nがコラッツ・角谷の問題で1になるまでのステップ数をf(n)とします。
1～2^20までの数でf(n)を求めて、f(n)が最大になるときのnとf(n)を表示してください。

たとえばn=9だと次のような数列をたどって、19ステップで1になります。
9->28->14->7->22->11->34->17->52->26->13->40->20->10->5->16->8->4->2->1
つまりf(9)=19です。

また、最大を求めた際の実行時間と環境を書いてください。

see: コラッツの問題の成り立つ範囲

お題投稿者です。
先日、放送大学を見ていたらこの問題が紹介されていたので、懐かしかったので出題してみました。

AthlonXP2500+で4.3秒でした。
2^25まで調べてみました。
これよりも大きい数になると、メモリが必死になるから、メモ化とは別のアプローチが必要になるかなぁ。
だいたいmaxに比例する感じですね。

max =  524288 time =  2.31200003624 sec result = [511935, 469]
max =  1048576 time =  4.28099989891 sec result = [837799, 524]
max =  2097152 time =  8.67200016975 sec result = [1723519, 556]
max =  4194304 time =  17.875 sec result = [3732423, 596]
max =  8388608 time =  37.0779998302 sec result = [6649279, 664]
max =  16777216 time =  74.2660000324 sec result = [15733191, 704]
max =  33554432 time =  153.812000036 sec result = [31466382, 705]

import time
import sys

def main(cMax):
    memo = [0] * (cMax)

    def _f(n):
        if n == 1:
            return 0
        if n < cMax and memo[n] != 0:
            return memo[n]
        if n % 2 == 0:
            step = _f(n/2) + 1
        else:
            step = _f(n*3 + 1) + 1
        if n < cMax:
            memo[n] = step
        return step

    m = [0,0]
    for x in xrange(1, cMax):
        if memo[x] == 0:
            _f(x)
            if memo[x] > m[1]:
                m =[x,memo[x]]

    return m

if __name__ == '__main__':
    for x in xrange(10,25+1):
        t = time.time()
        result = main(2**x)
        print "max = ", 2**x , "time = ", time.time() - t, "sec result =", result

Celeron 2GHz メモリ1GBで17秒ほどで答え出ました．

% time python korattu.py

524

python korattu.py 16.98s user 0.47s system 88% cpu 19.652 total

D={1:0}
def f(n):
    if D.has_key(n):pass
    elif n%2 == 0:D[n]=f(n/2)+1
    else: D[n]=f(3*n+1)+1
    return D[n]

if __name__=='__main__':
    step=0
    for i in xrange(1,2**20):
        step=max(step, f(i))
    print step

ステップ数が最大になる時のnを求めてませんでした. main部分を修正しました実行結果 (837799, 524)

if __name__=='__main__':
    step=(0,0)
    for i in xrange(1,2**20):
        tmp=i,f(i)
        if step[1] < tmp[1]:step=tmp
    print step

DouKaku?

コラッツ・角谷の問題

Posted feedbacks - Python

Index

Feed

Other

Link

Pathtraq