コラッツ予想に関するプログラム集。
2009/12/22
Collatz problem、コラッツの予想。自然数の奇数・偶数に対して所定の操作を繰り返すと、どんな自然数から出発しても最後に必ず1に到達するという予想であり、現時点で数学の未解決問題の1つ。
操作は単純で、0ではない自然数nに対して
を繰り返す。予想が正しければ、いかなる自然数nも、有限回の操作で1になる。
このページができる以前に少しの間だけ存在したJavaScriptプログラムの焼き直し的ページ。
2009/12/22
ある初期値に対するコラッツ予想を計算する最も単純なプログラム。JavaScriptによる一番簡単な書き出し再帰関数プログラムは以下の通り(2005年10月の日記より)。JavaScript実験場に貼りつけて実行すれば速やかに結果が表示される。
collatz = function(n){
document.writeln(n);
if(n>1){
if(n%2==0)collatz(n/2);
else collatz(3*n+1);
}
}
collatz(27);
これだけでは単純過ぎるので、計算桁数の上限リミットをHugeInt Ver.0.5 alpha5を用いて突破した。計算時間が許す限り、際限なく巨大な自然数に対してコラッツ予想を計算できる。手元の環境では適当な100桁の自然数の計算に0.7秒程度。また計算に関する処理とその有無を細かく設定できるようにし、この種の単純なアルゴリズムとしては豪華なものになっている。
計算したい自然数を入力して計算ボタンを押せば結果が表示される。通常では計算途中にJavaScriptの精度限界を超える253より大きな数が出現した場合、精度が保障できないため計算を中止するようになっている。精度限界以上の計算を行うときはHugeIntモードにチェックを入れることで巨大な整数を扱うことができる計算式に切り替わる。尚、この機能が任意なのは通常の計算に比べると余分な処理を行い速度が若干落ちるためである。HugeIntモードでは精度超過が発生しないため中止処理は存在しない。
コラッツの問題がコンピュータで検算されているのは、精々253付近である。このプログラムではこの値を大きく超える自然数を計算できるため、予想が成り立たない時自然数がループすることを検証する処理と、同じく予想が成り立たない時自然数が発散して計算が終了しない問題を解決する策が講じられている。更にその2つについて、個別に機能を無効化できる。検証処理は反復回数と同じだけの配列数と、要素検索の計算コストを必要とする。コラッツの予想が成り立つ前提では「検証処理を実行しない」にチェックすることで機能を無効化して高速化できる。一方、自然数が発散する対策は最大反復回数を制限することで達成している(下限は10000回、上限は検証を行う場合のみ1000000に制限される)。「最大反復回数を制限」のチェックを外すことで無効化でき、無制限に計算を続けることができる。
※JavaScriptを用いているため、これを有効にしなければ動かない。
2009/12/22?
未完成、建造中。