|
|
| 1行目: |
1行目: |
| − | [[Image:Collatz-graph-all-30-no27.svg|thumb|100px|これは30以下の整数(27のみ除く)の操作を表にしたもの。どの数も最終的に1となる。]]
| + | {{テンプレート:20180815sk}} |
| − | '''コラッツの問題'''(コラッツのもんだい、Collatz problem)は、[[数論]]の未解決問題のひとつである。1937年に[[ローター・コラッツ]]が問題を提示した。問題の結論の予想を指して'''コラッツの予想'''と言う。固有名詞に依拠しない表現としては'''3n+1問題'''とも言われ、初期にこの問題に取り組んだ研究者の名を冠して、'''[[角谷静夫|角谷(かくたに)]]の問題'''、'''[[米田信夫|米田]]の予想'''、'''[[スタニスワフ・ウラム|ウラム]]の予想'''、他には'''Syracuse問題'''などとも呼ばれる。数学者[[ポール・エルデシュ]]は「数学はまだこの種の問題に対する用意ができていない」と述べ、解決した人に500ドルを提供すると申し出た。
| |
| − | | |
| − | コンピュータを用いた計算により、5 × 2<sup>60</sup> までには反例がないことが確かめられている<ref>[http://sweet.ua.pt/tos/3x_plus_1.html Computational verification of the 3x+1 conjecture] (T. Oliveira e Silva)</ref>。
| |
| − | また、2011年度[[大学入試センター試験]]数学IIB第6問に題材として取り上げられた<ref>{{PDFlink|http://www.47news.jp/47topics/pdf/23sugaku2b_q.pdf}}</ref>。
| |
| − | | |
| − | == 問題の概要 ==
| |
| − | コラッツの問題は、「任意の正の[[整数]] ''n'' をとり、
| |
| − | *''n'' が[[偶数]]の場合、''n'' を 2 で割る
| |
| − | *''n'' が[[奇数]]の場合、''n'' に 3 をかけて 1 を足す
| |
| − | という操作を繰り返すと、どうなるか」というものである。「どんな初期値から始めても、有限回の操作のうちに必ず 1 に到達する(そして 1→4→2→1 というループに入る)」という主張が、コラッツの予想である。
| |
| − | | |
| − | 以下、もう少し詳しく定義する。
| |
| − | | |
| − | [[関数 (数学)|関数]] ''f'' を次のように定義する。
| |
| − | :<math>f(n) = \begin{cases} n/2 &\mbox{if } n \equiv 0 \\ 3n+1 & \mbox{if } n\equiv 1 \end{cases} \pmod{2}</math>
| |
| − | ここで任意の正の整数から開始し、上記の演算を繰り返し実行することにより数列を作る。各ステップでの結果は次ステップの関数 ''f''(''n'') の変数 ''n'' に代入される。数式で表現すると、以下のようになる：
| |
| − | :<math>a_i = \begin{cases}n & \mbox{for } i = 0 \\ f(a_{i-1}) & \mbox{for } i > 0\end{cases}</math>
| |
| − | このとき「初期値のとり方にかかわりなく、この操作を繰り返すと最終的に 1 に到達する」という主張が、コラッツの予想である。形式的に書くと、以下のようになる。
| |
| − | :<math> \forall n \isin \mathbb{N} > 0 \ \exists i \isin \mathbb{N}: (a_0 = n \Rightarrow a_i = 1)</math>
| |
| − | もしこの予想が誤りであるなら、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 × 2<sup>60</sup> = 5,764,607,523,034,234,880までは成り立つことがコンピュータで確認されている。この数値は、コンピュータのスピードアップとテスト技術の向上に伴って更新され続けている。
| |
| − | | |
| − | === ヒューリスティクス ===
| |
| − | 厳密な議論ではない[[ヒューリスティクス]]であるが、ステップを経るごとに数の大きさがどのようになるかを考察しよう。今、''n'' が偶数ならば、次のステップで大きさは半分になる。また、''n'' が奇数ならば、次のステップで 3''n'' + 1 になるが、これは必ず偶数であるから、その次に (3''n'' + 1)/2 になることまでは確定している。ここまでを一つのステップと解釈すれば、このステップで大きさは約 3/2 倍になる。1回のステップを経た後に偶数になるか、奇数になるかが半々であると考えると、1/2 の確率で数の大きさは 1/2 倍になり、残る 1/2 の確率で数の大きさは 3/2 倍になる。よって、1回のステップで、数の大きさは (1/2)<sup>1/2</sup> × (3/2)<sup>1/2</sup> 倍になると期待される。これは 1 より小さな値であるから、ステップを経るごとに「確率的に」小さくなると考えられる。この意味で、いつかは 1 に到達するとの予想は確からしい。
| |
| − | | |
| − | 確率論の言葉を用いるとこれは無限のステップ数を取る極限で1に平均収束するということであり、厳密には予想の確からしさとは無関係である。[[ストレンマイヤー]]は1957年にマルティンゲールの理論を用いて上記の議論を精密化し、任意のコロモゴルフ測度の下で有限ステップ内に数の大きさが1に[[概収束]](確率1で収束)することを証明した。
| |
| − | | |
| − | ==整数、有理数、複素数一般への変数nの拡張による問題の拡張==
| |
| − | コラッツの問題は、その代入される変数nを、自然数から、0や負の数を含む整数、有理数、複素数へと拡張することが可能である。
| |
| − | == 類似の問題 ==
| |
| − | 関数 ''f'' の定義を少し変えることにより、コラッツの問題の類似を考えることができる。
| |
| − | ===変数''n''が奇数の時の乗数の奇数一般への拡張による類似問題===
| |
| − | 例えば「任意の正の[[整数]] ''n'' に対して
| |
| − | *''n'' が偶数の場合、''n'' を 2 で割る
| |
| − | *''n'' が奇数の場合、''n'' に 2''m'' – 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'' が偶数の場合、''n'' を 2 で割る
| |
| − | *''n'' が奇数の場合、''n'' に 3をかけて 2''l'' - 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をかけて 2''l'' – 1 (''l'' ≥ 1) を足す
| |
| − | という操作を繰り返すと、有限回で1または2''l'' – 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にも到達しない。
| |
| − | | |
| − | ただし、上の、2''l'' – 1 (''l'' ≥ 1) が、0以上の整数''a''を用いて3<sup>''a''–1</sup> (''a'' ≥ 1) で表されるときには、上記のプロセスを繰り返せば、有限回数で1または3<sup>''a''–1</sup> (''a'' ≥ 1) に到達することは予想される。''a'' = 1の場合がコラッツの問題である。''a'' = 2の場合は、上記で''l'' = 2のケースである。
| |
| − | | |
| − | ===変数''n''が奇数の時の乗数と加算数双方の、奇数一般への拡張による類似問題===
| |
| − | 以上のことから、一般化は困難ではあるが、個別に考えるなら、さらに進んで、「任意の正の[[整数]] ''n'' に対して
| |
| − | *''n'' が偶数の場合、''n'' を 2 で割る
| |
| − | *''n'' が奇数の場合、''n'' に 2''m'' – 1 (''m'' ≥ 1) をかけて、2''l'' – 1 (''l'' ≥ 1) を足す
| |
| − | という操作を繰り返すとき、''n''、''m''、''l''の値に応じてどのような数列が展開されるか」
| |
| − | | |
| − | という問題にも拡張できるなど、コラッツの問題の類似問題の幅は広い。
| |
| − | | |
| − | == 参考文献 ==
| |
| − | {{reflist}}
| |
| − | | |
| − | | |
| − | | |
| − | == 関連文献 ==
| |
| − | *『数学100の問題』 日本評論社 ISBN 978-4535606142 「角谷の問題」として取り上げられている。
| |
| − | *『数学の魔法の宝箱』 [[イアン・スチュアート|イアン・スチュアート (数学者)]] ソフトバンク クリエイティブ ISBN 978-4-7973-5982-4：「コラッツ＝シラキュース＝ウラム問題」として紹介されている。
| |
| − | | |
| − | == 関連項目 ==
| |
| − | *[[タグシステム]]
| |
| − | | |
| − | == 外部リンク ==
| |
| − | *{{MathWorld|urlname=CollatzProblem|title=Collatz Problem}}
| |
| − | *[http://www.geocities.co.jp/HeartLand/2327/rada/korattsu.html コラッツ予想] コラッツ予想計算
| |
| − | *[http://www.usamimi.info/~geko/arch_acade/elf027_collatz/index.html コラッツ予想に関するプログラム集。] コラッツ予想計算、拡張問題にも対応可能。
| |
| − | *{{PDFlink|[http://web.archive.org/web/20120330191814/http://risweb2.ris.ac.jp/faculty/earth_env/yamasita/open/p-col.pdf コラッツ問題のある一般化について]}}（2012年3月30日時点の[[インターネットアーカイブ|アーカイブ]]）
| |
| − | *[http://boinc.thesonntags.com/collatz/ Collatz Conjecture] コラッツの問題を検証する為の[[分散コンピューティング]]
| |
| − | | |
| − | {{DEFAULTSORT:こらつつのもんたい}} | |
| − | [[Category:数論]]
| |
| − | [[Category:数学に関する記事]]
| |
| − | [[Category:整数の類]]
| |
| − | [[Category:予想]]
| |