「数学の未解決問題「コラッツ予想」の解決に1億2000万円の懸賞金。音圧爆上げくん」記事へのコメント

1000ステップ

[Anonymous Coward]

試しに1から10億までをチェックしてみたんだが、670617279 の時に 986 ステップかかったのが最長。
1000ステップを越えることはあるんだろうか?

Re:1000ステップ

[mfukuda (15975)]

下記論文で、FPGAで探索した例が載ってました。
　3x+1問題に対するFPGAの利用 [core.ac.uk],小島航,角谷浩享

1000ステップを超える例は以下の通り。
数、ステップ数
1008932249296230 1445
739448869367967 1187
31835572457967 1177
13179928405231 1122

ただ、検証サイト [casio.jp]で確認すると、最初のは413サイクルで1になるようだけど。ほかの3つは計算できなかった。

Wikipediaによると、2⁶⁸までは反例がないとのことなので、探索するならターゲットはそれ以上の数の奇数ですね。成立することを示すには証明しなきゃダメだけど、不成立することを示すなら反例を一つ示せばよい。ただ、反例1つみつけたら、ループするならそのループの周期の数だけ、発散するなら無限の数の反例が見つかることになる。反例がある可能性は低い感じ。

1/2は右1ビットシフト、3倍にして1足すのは左1ビットシフトしたのと加算して1足せばいいから、FPGAで一気に1000段くらい計算するハードウェアを作ればすぐ検証できそうな気もする。

Re:

[Anonymous Coward]

> すぐ検証できそうな気もする。
何を作っても愚直に計算するだけなら、ある有限値までしか検証出来ないよね。

Re:

[Anonymous Coward]

LibreOfficeで検算してみた。
1008932249296230 は 413回で1になった。
後の3つは計算途中で10の16乗を越えて概算になっている模様。
検証サイトでも同じような事情でエラーにしたのか?

Re:

[Anonymous Coward]

符号付64ビット整数がオーバーフローするみたい。
符号なしにしてチェックしたら

1008932249296230 : 412 ステップ
739448869367967 : 679 ステップ
31835572457967 : 798 ステップ
13179928405231 : 938 ステップ

になった。
下に出てくる
670617279 * 2^(1000 - 986) = 10987393499136 ではちょうど 1000ステップ。
670617279 * 2^(1000 - 986 + 1) = 21974786998272 では 1001ステップ。

Re:1000ステップ

[onetime_id (39093)]

https://qiita.com/keigo1450/items/d9605c94770e928409c0 [qiita.com]
のrubyでやってみると

$ ruby collaz.rb 1008932249296230 | tail -1
Steps: 412
$ ruby collaz.rb 739448869367967 | tail -1
Steps: 1505
$ ruby collaz.rb 31835572457967 | tail -1
Steps: 1547
$ ruby collaz.rb 13179928405231 | tail -1
Steps: 1349

でした。
# 結局元のPDFと違う。。。

$ ruby collaz.rb 1008932249296230 | egrep ".{20}" | head -3
Start: 1008932249296230

ruby collaz.rb 739448869367967 | egrep ".{20}" | head -3
Start: 739448869367967
10791515291244201214
16187272936866301822

$ ruby collaz.rb 31835572457967 | egrep ".{20}" | head -3
Start: 31835572457967
11173906961384413390
16760860442076620086

$ ruby collaz.rb 13179928405231 | egrep ".{20}" | head -3
Start: 13179928405231
13563449159449072048
14484015288923398738

なので、64bitだと後ろの3つはオーバーフローしてそうです。
2^64=1.84467441e19

Re:

[Anonymous Coward]

こんなとき、python が役に立つ。
整数計算だったらオーバーフローを気にしなくて済む。
2の100万乗とか一瞬で計算してくれるのだが、どうやって計算してるんだろう。

Re:

[Anonymous Coward]

整数がオーバーフローしないのはrubyもいっしょだ(笑)。Javascriptでも最近はBigIntが入ったのでちょっと書き換えたら行ける。

あと、とんでもなく大きな数乗はx^yなら、x²を2乗したらx⁴、それを2乗したらx⁸、それを2乗したらx¹⁶…、10回目ぐらいでx¹⁰²⁴、20回目ぐらいで、x^約100万、…と増やせるので、後は、xの右肩に乗ってる数字の合計が調度yになるよう、必要な分だけピックアップして掛ければ終了。ピックアップするのは、超雑に言うとyを2進数に直して0と1の列にして1のとこに該当する分。

Re:1000ステップ

[onetime_id (39093)]

例えば 670617279 * 2^(1000 - 986)は1000ステップを超えそうな気がする。

https://ja.wikipedia.org/wiki/%E3%82%B3%E3%83%A9%E3%83%83%E3%83%84%E3%... [wikipedia.org]
この予想は、初期値が268 ≈ 2.95×10²⁰までは成り立つことがコンピュータで確認されている。

らしく、670617279 * 2^(1000 - 986)=1.0987393e+13 らしいので成り立つことが確認されている範囲だと思うし。

Re:

[Anonymous Coward]

そりゃそうだ。
2の1000乗が1に収束するのに1000ステップ、2の10000乗なら10000ステップだ。
670617279 * 2 ^ 10000 だったら 986 + 10000 ステップ。

＃なんか計算違いをしている?

Re:

[Anonymous Coward]

670617279 * 2^(1000 - 986) = 670617279 * 2^14 だから、最初の14回は2で割り切れて、14回処理後は 670617279 になる。
670617279 から開始して986ステップで1になるのだから、14 + 986 = 1000ステップちょうどになる。