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 - Smalltalk

Squeak Smalltalk で。

1.0 GHz PowerPC、90 秒弱でした。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
| collatz result |

collatz := [:nn |
    | nSteps |
    nSteps := 0.
    [   nSteps := nSteps + 1.
        nn := nn even ifTrue: [nn / 2] ifFalse: [3 * nn + 1].
        nn = 1] whileFalse.
    nSteps].

^{[result := (1 to: (2 raisedTo: 20))
    inject: 0 -> 0
    into: [:max :mm | (collatz value: mm) -> mm max: max]] timeToRun. result}

"=> {87834 . 524->837799} "

Index

Feed

Other

Link

Pathtraq

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