コラッツの問題(予想)についての話です。
きっかけは、AIZU ONNLINE JUDGEのVolume1 - 0158から、"Collatz's Problem"の出題でした。
https://onlinejudge.u-aizu.ac.jp/problems/0158
まずはコラッツの問題(予想)について、Wikipediaによれば...
>コラッツの問題は、数論の未解決問題のひとつである。
>1937年にローター・コラッツが問題を提示した。
>問題の結論の予想を指してコラッツの予想と言う。
https://ja.wikipedia.org/wiki/コラッツの問題
>固有名詞に依拠しない表現としては3n+1問題とも言われ、初期にこの問題に取り組んだ研究者の名を冠して、角谷の問題、米田の予想、ウラムの予想、他にはSyracuse問題などとも呼ばれる。
で、問題の概要について...
>コラッツの問題は、「任意の正の整数 n をとり、
n が偶数の場合、n を 2 で割る
n が奇数の場合、n に 3 をかけて 1 を足す
という操作を繰り返すと、どうなるか」というものである。
>「どんな初期値から始めても、有限回の操作のうちに必ず 1 に到達する(そして 1→4→2→1 というループに入る)」という主張が、コラッツの予想である。
詳しい定義としては...
>関数 f を次のように定義する。
>ここで任意の正の整数から開始し、上記の演算を繰り返し実行することにより数列を作る。
各ステップでの結果は次ステップの関数 f(n) の変数 n に代入される。
>このとき「初期値のとり方にかかわりなく、この操作を繰り返すと最終的に 1 に到達する」という主張が、コラッツの予想である。
>形式的に書くと、以下のようになる。
>もしこの予想が誤りであるなら、1 を含まない数列を生成する初期値が存在するということになる。
>そのような数列は、1 を含まない繰り返し数列に突入するか、もしくは際限なく増大していくかのいずれかである。
>そのような数列はいまだ見つかっていない。
例としては...
>初期値を6にすると、6, 3, 10, 5, 16, 8, 4, 2, 1 という、1に到達する数列を得る。
>初期値を 11 とすると、11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 となり、1 に到達するまでにより長くかかる。
>初期値として 27 を選ぶと、数列は111ステップにまで及び、その値は最終的に 1 に到達する前に 9232 にまで増大する。
>コラッツの予想を証明するにあたっては、 初期値を奇数に限定してもかまわない。
なぜなら初期値が偶数の場合でも、コラッツの漸化式に従えば因数の 2 は最終的にすべて除去され、奇数になるからである。
コラッツの問題を研究した多くの数学者が「正しいだろう」と考えている論拠としては...
・経験的証拠
>この予想は、初期値が268 ≈ 2.95×1020までは成り立つことがコンピュータで確認されている。
>この数値は、コンピュータのスピードアップとテスト技術の向上に伴って更新され続けている。
>しかしこういったコンピューターでの検証は、予想が真であるという証拠にはならない。
>ポリア予想、メルテンス予想、スキューズ数の場合に示されているように、非常に大きな数において予想の反例が見つかることがある。
・ヒューリスティクス(発見的手法)
>今、n が偶数ならば、次のステップで大きさは半分になる。
>また、n が奇数ならば、次のステップで 3n + 1 になるが、これは必ず偶数であるから、その次に (3n + 1)/2 になることまでは確定している。
>ここまでを一つのステップと解釈すれば、このステップで大きさは約 3/2 倍になる。
>1回のステップを経た後に偶数になるか、奇数になるかが半々であると考えると、1/2 の確率で数の大きさは 1/2 倍になり、残る 1/2 の確率で数の大きさは 3/2 倍になる。
>よって、1回のステップで、数の大きさは (1/2)1/2 × (3/2)1/2 倍になると期待される。
>これは 1 より小さな値であるから、ステップを経るごとに「確率的に」小さくなると考えられる。
>この意味で、いつかは 1 に到達するとの予想は確からしい。
>確率論の言葉を用いるとこれは無限のステップ数を取る極限で1に平均収束するということであり、厳密には予想の確からしさとは無関係である。
はい、めっちゃ詳しくて、しかもわかりやすく解説してくれているので、とても勉強になりました。
そして、AIZU ONLINE JUDGEのVolume1 - 0158から、"Collatz's Problem"の出題では...
「整数 n を入力とし、結果が 1 になるまでに繰り返される操作の回数を出力するプログラムを作成してください」
整数 n は 1 以上でかつ計算を繰り返す途中の値が 1000000 以下となる程度の整数とします。
僕が作成、提出したコードは、以下のとおりです。
Aizu Online Judge in C++ #Volume1 - 0158 : Collatz's Problem
/* Aizu Online Judge in C++ #Volume1 - 0158 : Collatz's Problem https://onlinejudge.u-aizu.ac.jp/problems/0158 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ while(1){ int n; cin>>n; if(n==0){ return 0; } int cnt=0; for(int i=0;n!=1;i++){ if(n%2==0){ n/=2; }else{ n*=3; n+=1; } cnt++; } cout<<cnt<<endl; } }
それから、コラッツ予想の拡張については、すべての整数、奇数分母の有理数、複素数一般への変数nの拡張が、すでに考えられているみたいです。
また、類似の問題については...
>関数 f の定義を少し変えることにより、コラッツの問題の類似を考えることができる。
・変数nが奇数の時の乗数の奇数一般への拡張による類似問題
・変数nが奇数の時の加算数の奇数一般への拡張による類似問題
・変数nが奇数の時の乗数と加算数双方の、奇数一般への拡張による類似問題
>という問題にも拡張できるなど、コラッツの問題の類似問題の幅は広い。
きっとコラッツの予想が「必ず1になれ!」ってぐらいにシンプルだから、色々と考えやすいのだろうなーってか、考え始めちゃっているわー、今も。
うわぁー、これも沼だな!
設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/