コラッツの問題

コラッツの問題(コラッツのもんだい、Collatz problem)は、数論の未解決問題のひとつである。1937年にローター・コラッツが問題を提示した。問題の結論の予想を指してコラッツの予想と言う。固有名詞に依拠しない表現としては3n+1問題とも言われ、初期にこの問題に取り組んだ研究者の名を冠して、角谷(かくたに)の問題、米田の予想、ウラムの予想、他にはSyracuse問題などとも呼ばれる。数学者ポール・エルデシュは「数学はまだこの種の問題に対する用意ができていない」と述べ、解決した人に500ドルを提供すると申し出た。 コンピュータを用いた計算により、5 × 260 までには反例がないことが確かめられている。 また、2011年度大学入試センター試験数学IIB第6問に題材として取り上げられた。 コラッツの問題は、「任意の正の整数 n をとり、 n が偶数の場合、n を 2 で割る n が奇数の場合、n に 3 をかけて 1 を足す という操作を繰り返すと、どうなるか」というものである。「どんな初期値から始めても、有限回の操作のうちに必ず 1 に到達する(そして 1→4→2→1 というループに入る)」という主張が、コラッツの予想である。 以下、もう少し詳しく定義する。 関数 f を次のように定義する。 f ( n ) = { n / 2 if  n ≡ 0 3 n + 1 if  n ≡ 1 ( mod 2 ) {\displaystyle f(n)={\begin{cases}n/2&{\mbox{if }}n\equiv 0\\3n+1&{\mbox{if }}n\equiv 1\end{cases}}{\pmod {2}}} ここで任意の正の整数から開始し、上記の演算を繰り返し実行することにより数列を作る。各ステップでの結果は次ステップの関数 f(n) の変数 n に代入される。数式で表現すると、以下のようになる： a i = { n for  i = 0 f ( a i − 1 ) for  i > 0 {\displaystyle a_{i}={\begin{cases}n&{\mbox{for }}i=0\\f(a_{i-1})&{\mbox{for }}i>0\end{cases}}} このとき「初期値のとり方にかかわりなく、この操作を繰り返すと最終的に 1 に到達する」という主張が、コラッツの予想である。形式的に書くと、以下のようになる。 ∀ n ∈ N > 0   ∃ i ∈ N : ( a 0 = n ⇒ a i = 1 ) {\displaystyle \forall n\in \mathbb {N} >0\ \exists i\in \mathbb {N} :(a_{0}=n\Rightarrow a_{i}=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 にまで増大する。 27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1 コラッツの予想を証明するにあたっては、 初期値を奇数に限定してもかまわない。なぜなら初期値が偶数の場合でも、コラッツの漸化式に従えば因数の 2 は最終的にすべて除去され、奇数になるからである。 以下は擬似コードによるプログラミング例である。与えられた初期値に対するコラッツ数列を計算できる。 def collatz(n) show n if n.odd? and n > 1 collatz(3n + 1) else if n.even? collatz(n / 2) このプログラムは 1, 4, 2, 1 の無限サイクルを省くために 1 に到達すると停止するようになっている。もしコラッツ予想が正しければ、いかなる正の整数の初期値を与えても停止する。 この問題を、初期のコンピュータで計算することで研究したのがスタニスワフ・ウラムであった。 コラッツの予想は未解決だが、この問題を研究した多くの数学者は正しいだろうと考えている。そう予想される理由を以下に挙げる。 この予想は、初期値が 5 × 260 =  5,764,607,523,034,234,880までは成り立つことがコンピュータで確認されている。この数値は、コンピュータのスピードアップとテスト技術の向上に伴って更新され続けている。 厳密な議論ではないヒューリスティクスであるが、ステップを経るごとに数の大きさがどのようになるかを考察しよう。今、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に平均収束するということであり、厳密には予想の確からしさとは無関係である。ストレンマイヤーは1957年にマルティンゲールの理論を用いて上記の議論を精密化し、任意のコロモゴルフ測度の下で有限ステップ内に数の大きさが1に概収束(確率1で収束)することを証明した。 コラッツの問題は、その代入される変数nを、自然数から、0や負の数を含む整数、有理数、複素数へと拡張することが可能である。 関数 f の定義を少し変えることにより、コラッツの問題の類似を考えることができる。 例えば「任意の正の整数 n に対して n が偶数の場合、n を 2 で割る n が奇数の場合、n に 2m – 1 (m ≥ 1)をかけて 1 を足す という操作を繰り返すと、有限回で 1 に到達する」という命題を考える。m = 1 のとき(nが奇数なら単に1を足す)は、この命題が正しいことを簡単に証明できる。m = 2 の場合が上述のコラッツの問題である。m ≥ 3 の場合は、mの値とnの初期値によっては、1を含まない繰り返し数列、もしくは際限なく増大していく数列が得られるため、この命題は一般に成り立たない。たとえば m = 3 の場合、nの初期値を13に設定すると、13, 66, 33, 166, 83, 416, 208, 104, 52, 26, 13 という1を含まない数列のサイクルが得られる。これは上記のヒューリスティクスの観点からして、mが大きくなるほど1に到達する可能性は低くなると予想されることとも符合する。 また、もう一つの類似として、「任意の正の整数 n に対して n が偶数の場合、n を 2 で割る n が奇数の場合、n に 3をかけて 2l - 1 (l ≥ 1) を足す という操作を繰り返すと、有限回で 1 に到達する」という命題を考える。 ここで、l = 1 のときが上述のコラッツの問題である。しかし、l ≥ 2の場合、1を含まない繰り返し数列が得られる場合があるので、この命題は一般に成り立たない。 たとえば、l = 2として、初期値n = 43を与えた場合、43, 132, 66, 33, 102, 51, 156, 78, 39, 120, 60, 30, 15, 48, 24, 12, 6, 3, 12, 6, 3という数列が得られ、この命題は成り立たない。初期値nが1, 2などなら有限回で1に到達するが、他の初期値に対しては3, 12, 6, 3と、3を繰り返すサイクルになると思われる。そこでl = 2に対してコラッツの予想を応用し、「任意の正の整数 n に対して、上記の操作を行えば、有限回で1または3に到達する」という命題を代わりに立てれば、これが成り立つと予想される。 この二つの予想を一般化して、「任意の正の整数 n に対して n が偶数の場合、n を 2 で割る n が奇数の場合、n に 3をかけて 2l – 1 (l ≥ 1) を足す という操作を繰り返すと、有限回で1または2l – 1 (l ≥ 1) に到達する」という命題を立てたとしても、l ≥ 3以上の場合には、この命題は一般に成り立たない。たとえばl = 3の場合、任意の自然数nが1または5に到達するという命題になるが、n＝13の時、13, 44, 22, 11, 38, 19, 62, 31, 98, 49, 152, 76, 38, 19と、19を繰り返す無限ループになり、1にも5にも到達しない。 ただし、上の、2l – 1 (l ≥ 1) が、0以上の整数aを用いて3a–1 (a ≥ 1) で表されるときには、上記のプロセスを繰り返せば、有限回数で1または3a–1 (a ≥ 1) に到達することは予想される。a = 1の場合がコラッツの問題である。a = 2の場合は、上記でl = 2のケースである。 以上のことから、一般化は困難ではあるが、個別に考えるなら、さらに進んで、「任意の正の整数 n に対して n が偶数の場合、n を 2 で割る n が奇数の場合、n に 2m – 1 (m ≥ 1) をかけて、2l – 1 (l ≥ 1) を足す という操作を繰り返すとき、n、m、lの値に応じてどのような数列が展開されるか」 という問題にも拡張できるなど、コラッツの問題の類似問題の幅は広い。 ^ Computational verification of the 3x+1 conjecture (T. Oliveira e Silva) ^ 数学Ⅱ・数学B（2011年1月24日時点のインターネットアーカイブ） (PDF) - 【センター試験】２０１１年度大学入試センター試験速報－問題と正解（47NEWS）（2011年1月23日時点のインターネットアーカイブ） 『数学100の問題』 日本評論社 ISBN 978-4535606142 　「角谷の問題」として取り上げられている。 『数学の魔法の宝箱』 イアン・スチュアート (数学者) ソフトバンク クリエイティブ ISBN 978-4-7973-5982-4：「コラッツ＝シラキュース＝ウラム問題」として紹介されている。 タグシステム Weisstein, Eric W. "Collatz Problem". MathWorld（英語）. CS1 maint: Multiple names: authors list コラッツ予想 コラッツ予想計算 コラッツ予想に関するプログラム集。　コラッツ予想計算、拡張問題にも対応可能。 コラッツ問題のある一般化について (PDF) （2012年3月30日時点のアーカイブ） Collatz Conjecture コラッツの問題を検証する為の分散コンピューティング