DouKaku?beta

challenge コラッツ・角谷の問題 

任意の数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: コラッツの問題の成り立つ範囲

post comment

Posted feedbacks - D

f(837799) = 524

Processor: Athlon X2 3800+ / Memory: 1GB
Compiler: Digital Mars D Compiler v2.009
Process Time: 0:00:00.125 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import std.stdio;

void main() {
    uint i_max, x_max;
    foreach(i; 1 .. (1 << 20) + 1) {
        uint x = f(i);
        if(x_max < x) {
            x_max = x;
            i_max = i;
        }
    }
    writefln("f(%s) = %s", i_max, x_max);
}

uint f(const ulong n) {
    static uint[1 << 20] cache;
    
    if(n == 1) return 0;
    if(n < cache.length && cache[n])
        return cache[n];
    
    auto steps = (n % 2 == 0 ? f(n / 2) : f(n * 3 + 1)) + 1;
    if(n < cache.length) cache[n] = steps;
    return steps;
}

unittest {
    assert(f(9) == 19);
}

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]