数学界における未解決問題の1つ「コラッツ予想」に1億2000万円の懸賞金が提供された、というニュースがありました:
数学の未解決問題「コラッツ予想」に1億2000万円の懸賞金
このコラッツ予想とは、このような内容です:
正の整数:nに対して、以下(1)、(2)のルールで計算を繰り返していくと、どんな整数も最終的には必ず1になる
偶数だと2で割る(値は小さくなる)、奇数だと3を掛けて1を足す(値は大きくなる)という演算を繰り返す中で、大きくなり続けることはなく、必ず1に収束する、とも言いかえることができる予想です。試しに1から10までを計算するとこんな感じになります:
とりあえず1から10までの整数に関して予想は正しそうです。ただこの予想は「どんな整数であってもこれが成立する」ことを証明するか、「この予想が間違っていることを証明できる(予想に該当しない)整数の例を提示する」ことができれば1億2000万円、という賞金が用意されたことになります。
この予想が最終的に正しかったとしても、予想が間違っていたとしても(少なくとも現在までどちらも証明できた人は存在していないという事実からも)証明するのはかなり難しいことは間違い有りません。それでも興味ある方はぜひ1億2000万目指して頑張ってみてくださいw
で、今回のブログエントリで紹介するのは、このコラッツ予想をコンピュータで解くための準備段階のようなものです。 この予想が正しいかどうかをコンピュータを使ってできるところまで計算する(もし途中で1になることがない例外の数が見つかったら、それはそれで解けたことになっちゃいますけど・・・)ことに挑戦してみます。
で、この「コンピュータを使って計算」ですが、例えばこのようなコードを用意して実行してみると、10000 以下の整数については全て成立することがわかります:
じゃあ、後はこの 10000 と書かれた部分を 10000000000000000000000000000000000000000000000000 とかにして実行すると、もしも予想が正しくなければこのくらいの計算中に1つくらいは例外が見つかるんじゃなかろうか・・・ と考えたのですが、このロジックには2点無理がありました。
1点目は単純に時間が足りない可能性です。仮にこの中で例外となる数が存在していたとしても、それが判明するのがいつになるかはわからない(自分やその子、孫が生きているうちに終わる保証もない)、という実行時間の問題です。まあこちらは最悪並列化で高速化できないこともないですけど、、、
ただ問題はもう1点あります。それはコンピュータプログラムが整数として計算できる最大の数は決まっていて(例えば JavaScript の場合は 9007199254740991 で)、その数値を超えての演算は正しい結果が保証されないことです。つまり JavaScript で普通に計算した場合、計算途中経過も含めて 9007199254740991 以下の値まではこの予想が成立するかどうかを調べることはできるが、それ以上については言語仕様的に調べられない(途中計算に誤差が生じている可能性がある)、ということになるのでした。まあ一般的には 9000 兆強まで計算できれば充分なんでしょうけど。。
このプログラミング言語の仕様における最大整数値を超えて計算するのが「多倍長整数演算」と呼ばれているものです。処理速度が犠牲になることを理解した上で使う必要がありますが、言語仕様における最大整数値を超えてもあふれないように工夫しながら内部的に計算する、というもので、ライブラリ化されて公開されているものもあります(その代わり、計算方法なども通常の JavaScript のものとは別の方法になります)。今回はこの多倍長整数演算ライブラリを使って、任意の整数範囲でコラッツ予想が成立するかどうかを調べることができるようなアプリケーションを作って公開してみました。
※ちなみに今回の問題に関しては整数の範囲内だけで考えればいいのですが、小数を伴う場合はまた別の考え方をする必要があります。
なお、今回のアプリケーションを開発するにあたり、こちらで公開されている多倍長整数演算ライブラリを利用させていただきました:
http://mmua.html.xdomain.jp/bak/
作成したプログラムはこちらで公開していますが・・・
https://github.com/dotnsf/colaz
Github Pages を使って、アプリケーションも公開しています。ソースコードに興味はないけど、単にアプリを使ってみたい、という場合はこちらからどうぞ:
https://dotnsf.github.io/colaz/
ウェブブラウザでアプリケーションにアクセスすると以下のような画面になります:
ここで Start 欄(初期値は 1)と End 欄(初期値は 10000)に数値を入力して、Colaz ボタンをクリックすると、Start から End までの間でコラッツ予想が成立しているかどうかを多倍長整数演算で調べてくれます。ちなみに初期値のまま Colaz ボタンを押すとこんな感じになりました:
※[ ] に括られた数値が元の数値、その右が1になるまでのコラッツ演算の回数です。一番右の ( ) 内の数値はデバッグ用ということで。。
処理時間はパソコンの性能にもよりますが、私の PC で5秒もかからない程度でした。1 から 10000 までの整数でコラッツ予想は成立しているようでした:
ただ1~10000では多倍長整数演算でなくてもできる計算なので、あまり面白味はありません。では改めて Start 欄に JavaScript の演算上限値を超える1京(10000000000000000)を入力し、End 欄は1京1万(10000000000010000)を入力してみました。この状態で Colaz ボタンを押してみます:
クリック直後から CPU フル稼働で計算がはじまり、途中ほぼフリーズ状態になってこのようなダイアログが表示されますが、そのまま待機します:
およそ1分くらいで 10000 個ぶんの計算が完了し、結果が表示されました。値1つに対する計算回数はほぼ 450 を超え、 500 回を超えることもあり、かなり大変な演算になりましたが、この1万個の数値範囲でもコラッツ予想は正しかったことがわかります(例えば1京の場合は 255 回の演算で1になったことがわかります):
後はこれをうまく分散処理させて、大きな数字については分散環境で計算して・・・なんてことが実現できれば有志参加型の演算が行えていいなあ、と考えて構想しています(希望的観測)。
ちなみに、このライブラリを使った場合の演算方法の一部を紹介します。まず多倍長整数を扱うには普通の数値変数は使えないので、「整数は文字列で表記」して、「演算が必要になったら多倍長整数に変換」して演算することになります。四則演算や比較記号もそのままでは使えません。例えばコラッツ予想の変換ルール([A], [B] 部分)を関数化するとこのようになります:
数値として扱いきれない数値を文字列数値として扱い、演算時のみ多倍長整数変換して扱う、という処理が必要になります。なお、このコードでは計算途中の数値だけでなく、計算回数も(9000兆を超える可能性がゼロとは言い切れないので)多倍長整数で扱うようにしています。
これをずーーっと解いていってもコラッツ予想が正しいことの証明にはなりませんが、もし途中で例外(何回計算しても1にならない整数)が存在していたことが分かれば、予想が間違っていたことの証明にはなるので、いっそこちらにかけて計算してみる、というのはアリ、、かな?
数学の未解決問題「コラッツ予想」に1億2000万円の懸賞金
このコラッツ予想とは、このような内容です:
正の整数:nに対して、以下(1)、(2)のルールで計算を繰り返していくと、どんな整数も最終的には必ず1になる
(1) ・[A] nが偶数の場合 → nを2で割る ・[B] nが奇数の場合 → nに3を掛けて、1を足す (2) ・(1)の結果をnとして、(1)を繰り返す
偶数だと2で割る(値は小さくなる)、奇数だと3を掛けて1を足す(値は大きくなる)という演算を繰り返す中で、大きくなり続けることはなく、必ず1に収束する、とも言いかえることができる予想です。試しに1から10までを計算するとこんな感じになります:
1 : 1 2 : 2 -[A]-> 1 3 : 3 -[B]-> 10 -[A]-> 5 -[B]-> 16 -[A]-> 8 -[A]-> 4 -[A]-> 2 -[A]-> 1 4 : 4 -[A]-> 2 -[A]-> 1 5 : 5 -[B]-> 16 -[A]-> 8 -[A]-> 4 -[A]-> 2 -[A]-> 1 6 : 6 -[A]-> 3 -[B]-> 10 -[A]-> 5 -[B]-> 16 -[A]-> 8 -[A]-> 4 -[A]-> 2 -[A]-> 1 7 : 7 -[B]-> 22 -[A]-> 11 -[B]-> 34 -[A]-> 17 -[B]-> 52 -[A]-> 26 -[A]-> 13 -[B]-> 40 -[A]-> 20 -[A]-> 10 -[A]-> 5 -[B]-> 16 -[A]-> 8 -[A]-> 4 -[A]-> 2 -[A]-> 1 8 : 8 -[A]-> 4 -[A]-> 2 -[A]-> 1 9 : 9 -[B]-> 28 -[A]-> 14 -[A]-> 7 -[B]-> 22 -[A]-> 11 -[B]-> 34 -[A]-> 17 -[B]-> 52 -[A]-> 26 -[A]-> 13 -[B]-> 40 -[A]-> 20 -[A]-> 10 -[A]-> 5 -[B]-> 16 -[A]-> 8 -[A]-> 4 -[A]-> 2 -[A]-> 1 10 : 10 -[A]-> 5 -[B]-> 16 -[A]-> 8 -[A]-> 4 -[A]-> 2 -[A]-> 1
とりあえず1から10までの整数に関して予想は正しそうです。ただこの予想は「どんな整数であってもこれが成立する」ことを証明するか、「この予想が間違っていることを証明できる(予想に該当しない)整数の例を提示する」ことができれば1億2000万円、という賞金が用意されたことになります。
この予想が最終的に正しかったとしても、予想が間違っていたとしても(少なくとも現在までどちらも証明できた人は存在していないという事実からも)証明するのはかなり難しいことは間違い有りません。それでも興味ある方はぜひ1億2000万目指して頑張ってみてくださいw
で、今回のブログエントリで紹介するのは、このコラッツ予想をコンピュータで解くための準備段階のようなものです。 この予想が正しいかどうかをコンピュータを使ってできるところまで計算する(もし途中で1になることがない例外の数が見つかったら、それはそれで解けたことになっちゃいますけど・・・)ことに挑戦してみます。
で、この「コンピュータを使って計算」ですが、例えばこのようなコードを用意して実行してみると、10000 以下の整数については全て成立することがわかります:
function colaz( n ){ if( n % 2 == 0 ){ return ( n / 2 ); }else{ return ( n * 3 + 1 ); } } for( var i = 1; i <= 10000; i ++ ){ var x = i; while( x != 1 ){ if( x == 1 ){ console.log( i + ' : OK' ); break; }else{ x = colaz( x ); } } }
じゃあ、後はこの 10000 と書かれた部分を 10000000000000000000000000000000000000000000000000 とかにして実行すると、もしも予想が正しくなければこのくらいの計算中に1つくらいは例外が見つかるんじゃなかろうか・・・ と考えたのですが、このロジックには2点無理がありました。
1点目は単純に時間が足りない可能性です。仮にこの中で例外となる数が存在していたとしても、それが判明するのがいつになるかはわからない(自分やその子、孫が生きているうちに終わる保証もない)、という実行時間の問題です。まあこちらは最悪並列化で高速化できないこともないですけど、、、
ただ問題はもう1点あります。それはコンピュータプログラムが整数として計算できる最大の数は決まっていて(例えば JavaScript の場合は 9007199254740991 で)、その数値を超えての演算は正しい結果が保証されないことです。つまり JavaScript で普通に計算した場合、計算途中経過も含めて 9007199254740991 以下の値まではこの予想が成立するかどうかを調べることはできるが、それ以上については言語仕様的に調べられない(途中計算に誤差が生じている可能性がある)、ということになるのでした。まあ一般的には 9000 兆強まで計算できれば充分なんでしょうけど。。
このプログラミング言語の仕様における最大整数値を超えて計算するのが「多倍長整数演算」と呼ばれているものです。処理速度が犠牲になることを理解した上で使う必要がありますが、言語仕様における最大整数値を超えてもあふれないように工夫しながら内部的に計算する、というもので、ライブラリ化されて公開されているものもあります(その代わり、計算方法なども通常の JavaScript のものとは別の方法になります)。今回はこの多倍長整数演算ライブラリを使って、任意の整数範囲でコラッツ予想が成立するかどうかを調べることができるようなアプリケーションを作って公開してみました。
※ちなみに今回の問題に関しては整数の範囲内だけで考えればいいのですが、小数を伴う場合はまた別の考え方をする必要があります。
なお、今回のアプリケーションを開発するにあたり、こちらで公開されている多倍長整数演算ライブラリを利用させていただきました:
http://mmua.html.xdomain.jp/bak/
作成したプログラムはこちらで公開していますが・・・
https://github.com/dotnsf/colaz
Github Pages を使って、アプリケーションも公開しています。ソースコードに興味はないけど、単にアプリを使ってみたい、という場合はこちらからどうぞ:
https://dotnsf.github.io/colaz/
ウェブブラウザでアプリケーションにアクセスすると以下のような画面になります:
ここで Start 欄(初期値は 1)と End 欄(初期値は 10000)に数値を入力して、Colaz ボタンをクリックすると、Start から End までの間でコラッツ予想が成立しているかどうかを多倍長整数演算で調べてくれます。ちなみに初期値のまま Colaz ボタンを押すとこんな感じになりました:
※[ ] に括られた数値が元の数値、その右が1になるまでのコラッツ演算の回数です。一番右の ( ) 内の数値はデバッグ用ということで。。
処理時間はパソコンの性能にもよりますが、私の PC で5秒もかからない程度でした。1 から 10000 までの整数でコラッツ予想は成立しているようでした:
ただ1~10000では多倍長整数演算でなくてもできる計算なので、あまり面白味はありません。では改めて Start 欄に JavaScript の演算上限値を超える1京(10000000000000000)を入力し、End 欄は1京1万(10000000000010000)を入力してみました。この状態で Colaz ボタンを押してみます:
クリック直後から CPU フル稼働で計算がはじまり、途中ほぼフリーズ状態になってこのようなダイアログが表示されますが、そのまま待機します:
およそ1分くらいで 10000 個ぶんの計算が完了し、結果が表示されました。値1つに対する計算回数はほぼ 450 を超え、 500 回を超えることもあり、かなり大変な演算になりましたが、この1万個の数値範囲でもコラッツ予想は正しかったことがわかります(例えば1京の場合は 255 回の演算で1になったことがわかります):
後はこれをうまく分散処理させて、大きな数字については分散環境で計算して・・・なんてことが実現できれば有志参加型の演算が行えていいなあ、と考えて構想しています(希望的観測)。
ちなみに、このライブラリを使った場合の演算方法の一部を紹介します。まず多倍長整数を扱うには普通の数値変数は使えないので、「整数は文字列で表記」して、「演算が必要になったら多倍長整数に変換」して演算することになります。四則演算や比較記号もそのままでは使えません。例えばコラッツ予想の変換ルール([A], [B] 部分)を関数化するとこのようになります:
function colaz_function( str ){ var x = Big( str ); // 多倍長整数変換 if( x.mod( 2 ).eq( 0 ) ){ // 偶数(2で割った余りが0)か? x = x.div( 2 ); // 偶数の場合は2で割る }else{ x = x.mul( 3 ).add( 1 ); // 奇数の場合は3をかけて1を足す } return x.toString(); // 多倍長整数を文字列に変換した結果を返す }
数値として扱いきれない数値を文字列数値として扱い、演算時のみ多倍長整数変換して扱う、という処理が必要になります。なお、このコードでは計算途中の数値だけでなく、計算回数も(9000兆を超える可能性がゼロとは言い切れないので)多倍長整数で扱うようにしています。
これをずーーっと解いていってもコラッツ予想が正しいことの証明にはなりませんが、もし途中で例外(何回計算しても1にならない整数)が存在していたことが分かれば、予想が間違っていたことの証明にはなるので、いっそこちらにかけて計算してみる、というのはアリ、、かな?
コメント
コメント一覧 (2)
言われて気付きました。発散した場合は(処理が終了しないので)CPU が 100% のまま何も表示されないですね。。 なので何も表示されない時間がしばらく続くようであれば発散している可能性がありますね。。