アカウント名:
パスワード:
試しに1から10億までをチェックしてみたんだが、670617279 の時に 986 ステップかかったのが最長。1000ステップを越えることはあるんだろうか?
> すぐ検証できそうな気もする。何を作っても愚直に計算するだけなら、ある有限値までしか検証出来ないよね。
LibreOfficeで検算してみた。1008932249296230 は 413回で1になった。後の3つは計算途中で10の16乗を越えて概算になっている模様。検証サイトでも同じような事情でエラーにしたのか?
符号付64ビット整数がオーバーフローするみたい。符号なしにしてチェックしたら
1008932249296230 : 412 ステップ739448869367967 : 679 ステップ31835572457967 : 798 ステップ13179928405231 : 938 ステップ
になった。下に出てくる670617279 * 2^(1000 - 986) = 10987393499136 ではちょうど 1000ステップ。670617279 * 2^(1000 - 986 + 1) = 21974786998272 では 1001ステップ。
https://qiita.com/keigo1450/items/d9605c94770e928409c0 [qiita.com]のrubyでやってみると
$ ruby collaz.rb 1008932249296230 | tail -1Steps: 412$ ruby collaz.rb 739448869367967 | tail -1Steps: 1505$ ruby collaz.rb 31835572457967 | tail -1Steps: 1547$ ruby collaz.rb 13179928405231 | tail -1Steps: 1349
でした。# 結局元のPDFと違う。。。
$ ruby collaz.rb 1008932249296230 | egrep ".{20}" | head -3Start: 1008932249296230
ruby collaz.rb 739448869367967 | egrep ".{20}" | head -3Start: 7394488693679671079151529124420121416187272936866301822
$ ruby collaz.rb 31835572457967 | egrep ".{20}" | head -3Start: 318355724579671117390696138441339016760860442076620086
$ ruby collaz.rb 13179928405231 | egrep ".{20}" | head -3Start: 131799284052311356344915944907204814484015288923398738
なので、64bitだと後ろの3つはオーバーフローしてそうです。2^64=1.84467441e19
こんなとき、python が役に立つ。整数計算だったらオーバーフローを気にしなくて済む。2の100万乗とか一瞬で計算してくれるのだが、どうやって計算してるんだろう。
整数がオーバーフローしないのはrubyもいっしょだ(笑)。Javascriptでも最近はBigIntが入ったのでちょっと書き換えたら行ける。
あと、とんでもなく大きな数乗はxyなら、x2を2乗したらx4、それを2乗したらx8、それを2乗したらx16…、10回目ぐらいでx1024、20回目ぐらいで、x約100万、…と増やせるので、後は、xの右肩に乗ってる数字の合計が調度yになるよう、必要な分だけピックアップして掛ければ終了。ピックアップするのは、超雑に言うとyを2進数に直して0と1の列にして1のとこに該当する分。
例えば 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×1020までは成り立つことがコンピュータで確認されている。
らしく、670617279 * 2^(1000 - 986)=1.0987393e+13 らしいので成り立つことが確認されている範囲だと思うし。
そりゃそうだ。2の1000乗が1に収束するのに1000ステップ、2の10000乗なら10000ステップだ。670617279 * 2 ^ 10000 だったら 986 + 10000 ステップ。
＃なんか計算違いをしている?
670617279 * 2^(1000 - 986) = 670617279 * 2^14 だから、最初の14回は2で割り切れて、14回処理後は 670617279 になる。670617279 から開始して986ステップで1になるのだから、14 + 986 = 1000ステップちょうどになる。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
Stay hungry, Stay foolish. -- Steven Paul Jobs
1000ステップ (スコア:0)
試しに1から10億までをチェックしてみたんだが、670617279 の時に 986 ステップかかったのが最長。
1000ステップを越えることはあるんだろうか?
Re:1000ステップ (スコア:2)
3x+1問題に対するFPGAの利用 [core.ac.uk],小島航,角谷浩享
1000ステップを超える例は以下の通り。
数、ステップ数
1008932249296230 1445
739448869367967 1187
31835572457967 1177
13179928405231 1122
ただ、検証サイト [casio.jp]で確認すると、最初のは413サイクルで1になるようだけど。ほかの3つは計算できなかった。
Wikipediaによると、268までは反例がないとのことなので、探索するならターゲットはそれ以上の数の奇数ですね。成立することを示すには証明しなきゃダメだけど、不成立することを示すなら反例を一つ示せばよい。ただ、反例1つみつけたら、ループするならそのループの周期の数だけ、発散するなら無限の数の反例が見つかることになる。反例がある可能性は低い感じ。
1/2は右1ビットシフト、3倍にして1足すのは左1ビットシフトしたのと加算して1足せばいいから、FPGAで一気に1000段くらい計算するハードウェアを作ればすぐ検証できそうな気もする。
Re: (スコア:0)
> すぐ検証できそうな気もする。
何を作っても愚直に計算するだけなら、ある有限値までしか検証出来ないよね。
Re: (スコア:0)
LibreOfficeで検算してみた。
1008932249296230 は 413回で1になった。
後の3つは計算途中で10の16乗を越えて概算になっている模様。
検証サイトでも同じような事情でエラーにしたのか?
Re: (スコア:0)
符号付64ビット整数がオーバーフローするみたい。
符号なしにしてチェックしたら
1008932249296230 : 412 ステップ
739448869367967 : 679 ステップ
31835572457967 : 798 ステップ
13179928405231 : 938 ステップ
になった。
下に出てくる
670617279 * 2^(1000 - 986) = 10987393499136 ではちょうど 1000ステップ。
670617279 * 2^(1000 - 986 + 1) = 21974786998272 では 1001ステップ。
Re:1000ステップ (スコア:2)
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: (スコア:0)
こんなとき、python が役に立つ。
整数計算だったらオーバーフローを気にしなくて済む。
2の100万乗とか一瞬で計算してくれるのだが、どうやって計算してるんだろう。
Re: (スコア:0)
整数がオーバーフローしないのはrubyもいっしょだ(笑)。Javascriptでも最近はBigIntが入ったのでちょっと書き換えたら行ける。
あと、とんでもなく大きな数乗はxyなら、x2を2乗したらx4、それを2乗したらx8、それを2乗したらx16…、10回目ぐらいでx1024、20回目ぐらいで、x約100万、…と増やせるので、後は、xの右肩に乗ってる数字の合計が調度yになるよう、必要な分だけピックアップして掛ければ終了。ピックアップするのは、超雑に言うとyを2進数に直して0と1の列にして1のとこに該当する分。
Re:1000ステップ (スコア:2)
例えば 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×1020までは成り立つことがコンピュータで確認されている。
らしく、670617279 * 2^(1000 - 986)=1.0987393e+13 らしいので成り立つことが確認されている範囲だと思うし。
Re: (スコア:0)
そりゃそうだ。
2の1000乗が1に収束するのに1000ステップ、2の10000乗なら10000ステップだ。
670617279 * 2 ^ 10000 だったら 986 + 10000 ステップ。
＃なんか計算違いをしている?
Re: (スコア:0)
670617279 * 2^(1000 - 986) = 670617279 * 2^14 だから、最初の14回は2で割り切れて、14回処理後は 670617279 になる。
670617279 から開始して986ステップで1になるのだから、14 + 986 = 1000ステップちょうどになる。