数学界における未解決問題の１つ「コラッツ予想」に１億２０００万円の懸賞金が提供された、というニュースがありました：
数学の未解決問題「コラッツ予想」に1億2000万円の懸賞金

このコラッツ予想とは、このような内容です：
正の整数：ｎに対して、以下（１）、（２）のルールで計算を繰り返していくと、どんな整数も最終的には必ず１になる

（１）
　・[A] ｎが偶数の場合　→　ｎを２で割る
　・[B] ｎが奇数の場合　→　ｎに３を掛けて、１を足す
（２）
　・（１）の結果をｎとして、（１）を繰り返す

偶数だと２で割る（値は小さくなる）、奇数だと３を掛けて１を足す（値は大きくなる）という演算を繰り返す中で、大きくなり続けることはなく、必ず１に収束する、とも言いかえることができる予想です。試しに１から１０までを計算するとこんな感じになります：

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

とりあえず１から１０までの整数に関して予想は正しそうです。ただこの予想は「どんな整数であってもこれが成立する」ことを証明するか、「この予想が間違っていることを証明できる（予想に該当しない）整数の例を提示する」ことができれば１億２０００万円、という賞金が用意されたことになります。


この予想が最終的に正しかったとしても、予想が間違っていたとしても（少なくとも現在までどちらも証明できた人は存在していないという事実からも）証明するのはかなり難しいことは間違い有りません。それでも興味ある方はぜひ１億２０００万目指して頑張ってみてくださいｗ


で、今回のブログエントリで紹介するのは、このコラッツ予想をコンピュータで解くための準備段階のようなものです。　この予想が正しいかどうかをコンピュータを使ってできるところまで計算する（もし途中で１になることがない例外の数が見つかったら、それはそれで解けたことになっちゃいますけど・・・）ことに挑戦してみます。

で、この「コンピュータを使って計算」ですが、例えばこのようなコードを用意して実行してみると、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 とかにして実行すると、もしも予想が正しくなければこのくらいの計算中に１つくらいは例外が見つかるんじゃなかろうか・・・　と考えたのですが、このロジックには２点無理がありました。

１点目は単純に時間が足りない可能性です。仮にこの中で例外となる数が存在していたとしても、それが判明するのがいつになるかはわからない（自分やその子、孫が生きているうちに終わる保証もない）、という実行時間の問題です。まあこちらは最悪並列化で高速化できないこともないですけど、、、　

ただ問題はもう１点あります。それはコンピュータプログラムが整数として計算できる最大の数は決まっていて（例えば 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 ボタンを押すとこんな感じになりました：


※[ ] に括られた数値が元の数値、その右が１になるまでのコラッツ演算の回数です。一番右の ( ) 内の数値はデバッグ用ということで。。


処理時間はパソコンの性能にもよりますが、私の PC で５秒もかからない程度でした。1 から 10000 までの整数でコラッツ予想は成立しているようでした：



ただ１～１００００では多倍長整数演算でなくてもできる計算なので、あまり面白味はありません。では改めて Start 欄に JavaScript の演算上限値を超える１京(10000000000000000)を入力し、End 欄は１京１万(10000000000010000)を入力してみました。この状態で Colaz ボタンを押してみます：



クリック直後から CPU フル稼働で計算がはじまり、途中ほぼフリーズ状態になってこのようなダイアログが表示されますが、そのまま待機します：



およそ１分くらいで 10000 個ぶんの計算が完了し、結果が表示されました。値１つに対する計算回数はほぼ 450 を超え、 500 回を超えることもあり、かなり大変な演算になりましたが、この１万個の数値範囲でもコラッツ予想は正しかったことがわかります（例えば１京の場合は 255 回の演算で１になったことがわかります）：





後はこれをうまく分散処理させて、大きな数字については分散環境で計算して・・・なんてことが実現できれば有志参加型の演算が行えていいなあ、と考えて構想しています（希望的観測）。


ちなみに、このライブラリを使った場合の演算方法の一部を紹介します。まず多倍長整数を扱うには普通の数値変数は使えないので、「整数は文字列で表記」して、「演算が必要になったら多倍長整数に変換」して演算することになります。四則演算や比較記号もそのままでは使えません。例えばコラッツ予想の変換ルール（[A], [B] 部分）を関数化するとこのようになります：

function colaz_function( str ){
  var x = Big( str );                 // 多倍長整数変換
  if( x.mod( 2 ).eq( 0 ) ){           // 偶数（２で割った余りが０）か？
    x = x.div( 2 );                   // 偶数の場合は２で割る
  }else{
    x = x.mul( 3 ).add( 1 );          // 奇数の場合は３をかけて１を足す
  }

  return x.toString();                // 多倍長整数を文字列に変換した結果を返す
}

数値として扱いきれない数値を文字列数値として扱い、演算時のみ多倍長整数変換して扱う、という処理が必要になります。なお、このコードでは計算途中の数値だけでなく、計算回数も（9000兆を超える可能性がゼロとは言い切れないので）多倍長整数で扱うようにしています。


これをずーーっと解いていってもコラッツ予想が正しいことの証明にはなりませんが、もし途中で例外（何回計算しても１にならない整数）が存在していたことが分かれば、予想が間違っていたことの証明にはなるので、いっそこちらにかけて計算してみる、というのはアリ、、かな？

 

タグ ：

#bigint

#colaz