コラッツの問題とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > コラッツの問題の意味・解説 

コラッツの問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/02/20 09:55 UTC 版)

コラッツマップ下の軌道を有向グラフにしたもの。コラッツ予想は、すべてのパスが1に至るということと同値である。

コラッツの問題(コラッツのもんだい、Collatz problem)は、数論の未解決問題のひとつである。問題の結論の予想を指してコラッツ予想と言う。伝統的にローター・コラッツの名を冠されて呼ばれる[1]が、固有名詞に依拠しない表現としては3n+1問題とも言われ、また初期にこの問題に取り組んだ研究者や場所の名を冠して、角谷の問題米田の予想ウラムの予想シラキュース問題などとも呼ばれる。

数学者ポール・エルデシュは「数学はまだこの種の問題に対する用意ができていない」と述べた。また、ジェフリー・ラガリアスは2010年に、コラッツの予想は「非常に難しい問題であり、現代の数学では完全に手が届かない」と述べた[2]

2019年9月、テレンス・タオはコラッツの問題がほとんどすべての正の整数においてほとんど正しいとするプレプリントを発表し[3][4]、論文は2022年5月に出版された[5]

概要

1から9999までの数に対して、1にいたるまでのステップ数をグラフにしたもの。
1から108までの、1に至るまでのステップ数のヒストグラム。x軸がステップ数で、頻度がy軸である。
2から107までの、1にいたるまでのステップ数をグラフにしたもの。
ステップ数: 250, 1000, 4000, 20000, 100000, 500000までをそれぞれグラフ化

任意の正の整数 n に対して、以下で定められる操作について考える。

  • n偶数の場合、n を 2 で割る
  • n奇数の場合、n に 3 をかけて 1 を足す

このとき、「どんな初期値から始めても、有限回の操作のうちに必ず 1 に到達する(そして 1→4→2→1 というループに入る)」という主張が、コラッツの予想である。

モジュラ計算の表記を用いて、上記の操作を関数 f として定義する。

初期値27のときの ai の値のグラフ

歴史

1930年代ごろ、学生であったコラッツは数論的関数を有向グラフとして表現して、そのグラフの性質が関数のふるまいとどのように関連付けられるかに興味を持った。この時の彼のノートには、現在知られるものとは異なる関数について調べられている。コラッツはこれらの関数についての問題を出版することはなかったが、1950年の国際数学者会議をきっかけに広くこの問題が知られるようになり、1963年に初めて (1930年代にコラッツが研究していた形のものが) 紙面に取りあげられた[1]。その後、この問題に興味を持った数学者によって研究される間に、様々な別名を得ることとなった。「ハッセのアルゴリズム」はヘルムート・ハッセに、「シラキュース問題」はシラキュース大学に、「角谷の問題」は角谷静夫に、「ウラムの問題」はスタニスワフ・ウラムに由来する[1]

コラッツ予想の解決にはいくつかの懸賞金がかけられており、コクセターが50ドル、エルデシュが500ドル、ブライアン・スウェイツ (Bryan Thwaitesは1000ポンドを申し出ている。

2011年度大学入試センター試験数学IIB第6問に題材として取り上げられた[7]

2019年、テレンス・タオは「limN→∞ f(N) = +∞ を満たす任意の関数 f : ℕ+ → ℝ について、N から始まるコラッツ数列の最小値は (Logarithmic densityの意味で) ほとんど全ての自然数 N において f(N) より小さい」ことを証明し[3]、コラッツ予想は「『ほとんど』全ての自然数で『ほとんど』正しい」[4]ことが示された。帰結として例えば、N から始まるコラッツ数列の最小値はほとんど全ての自然数 N において log log log log N より小さくなることが従う[3]

2021年7月7日、株式会社音圧爆上げくんが、「コラッツ予想の真偽を明らかにした方に懸賞金1億2000万円を支払います」と発表した[8][9]

この予想を支持する論拠

コラッツの予想は未解決だが、この問題を研究した多くの数学者は正しいだろうと考えている。そう予想される理由を以下に挙げる。

経験的証拠

この予想は、初期値が268 ≈ 2.95×1020までは成り立つことがコンピュータで確認されている[10]。この数値は、コンピュータのスピードアップとテスト技術の向上に伴って更新され続けている。

しかしこういったコンピューターでの検証は、予想が真であるという証拠にはならない。ポリア予想メルテンス予想英語版スキューズ数の場合に示されているように、非常に大きな数において予想の反例が見つかることがある。

ヒューリスティクス

厳密な議論ではないヒューリスティクスであるが、ステップを経るごとに数の大きさがどのようになるかを考察する。今、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で収束)することを証明した。[要出典]

コラッツの数列を計算するプログラミング例

以下は擬似コードによるプログラミング例である。与えられた初期値に対するコラッツ数列を計算できる。

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 に到達すると停止するようになっている。もしコラッツ予想が正しければ、いかなる正の整数の初期値を与えても停止する。

この問題を、初期のコンピュータで計算することで研究したのがスタニスワフ・ウラムであった。

サイクル

n が奇数であるときに 3n + 1 は必ず偶数になることから、コラッツ写像の「ショートカット」形式が次の定義で与えられる:

ボトムアップ方式で作成した21ステップまでのコラッツグラフ 。グラフには、軌道長が21以下のすべての数値が含まれている。

別のアプローチをとってみる:ボトムアップ方式でいわゆるコラッツグラフを作成してみる。 コラッツグラフは、以下のように操作を逆にして定義する。

実関数として拡張したコラッツ写像上で、コラッツ数列10-5-8-4-2-1-2-1-2-1-...をクモの巣図法で表示したもの。

コラッツ写像は、次の式で定義される滑らかな関数を整数に制限したものと見なせる:

複素コラッツ写像のジュリア集合。色がついている点はすべて無限遠へ発散する。

Letherman, Schleicher および Wood はこの関数の研究を複素平面へと拡張した[20]。ほとんどの複素平面上の点は無限遠へと発散するが、境界となるジュリア集合フラクタル図形を描く。

検証計算の最適化

時間と空間のトレードオフ

上記の パリティシーケンス により、コラッツ数列の計算の高速化が可能である。

(パリティシーケンス節の f 関数を使ったとして)k ステップ先にジャンプするために、まず現在の数値を2つに分割する: b(2進数表記で下位 k ビット)と、a(残りの上位ビット)。k ステップをジャンプした結果は以下になる:

最初の1000個の数字の数列を示す有向グラフ。
  • x軸は初期値を表し、y軸は、1に至るまでの間での最大値を示す。このプロットでは、y軸の範囲を制限している:いくつかのxでは、途中の最大値が2.7×107にもなる。(x = 9663の場合)
  • 20ステップ未満のすべてのツリー。
  • 参考文献

    関連文献

    関連項目

    外部リンク

    脚注

    1. ^ a b c d e f g Lagarias, Jeffrey C. (1985). “The 3x + 1 problem and its generalizations”. en:The American Mathematical Monthly 92 (1): 3–23. doi:10.1080/00029890.1985.11971528. JSTOR 2322189. 
    2. ^ Lagarias 2010, p. 4.
    3. ^ a b c Almost all orbits of the Collatz map attain almost bounded values”. arXiv (2019年9月8日). 2021年10月15日閲覧。
    4. ^ a b Hartnett, Kevin (2019年12月11日). “Mathematician Proves Huge Result on ‘Dangerous’ Problem” (英語). Quanta Magazine. オリジナルの2021年10月8日時点におけるアーカイブ。. https://web.archive.org/web/20211008005902/https://www.quantamagazine.org/mathematician-proves-huge-result-on-dangerous-problem-20191211 2022年2月20日閲覧。 
    5. ^ Tao, Terence (2022). “Almost all orbits of the Collatz map attain almost bounded values”. Forum of Mathematics, Pi 10: E12. doi:10.1017/fmp.2022.8. 
    6. ^ Barina, D. Convergence verification of the Collatz problem. J Supercomput (2020). https://doi.org/10.1007/s11227-020-03368-x
    7. ^ 数学Ⅱ・数学B(2011年1月24日時点のインターネットアーカイブ) (PDF) - 【センター試験】2011年度大学入試センター試験速報-問題と正解(47NEWS)(2011年1月23日時点のインターネットアーカイブ)
    8. ^ コラッツ予想 懸賞金1億2000万円”. Mathprize. Mathprize (2021年7月7日). 2022年1月21日時点のオリジナルよりアーカイブ。2022年2月21日閲覧。
    9. ^ 数学者も恐れる「ハマると病む難問」 解けたら1億円、企業が懸賞金”. 朝日新聞デジタル. 朝日新聞社 (2021年9月24日). 2021年9月15日時点のオリジナルよりアーカイブ。2022年2月21日閲覧。
    10. ^ Barina, David (2020). “Convergence verification of the Collatz problem”. The Journal of Supercomputing. doi:10.1007/s11227-020-03368-x. 
    11. ^ Eliahou, Shalom (1993-08-01). “The 3x+1 problem: new lower bounds on nontrivial cycle lengths”. Discrete Mathematics 118 (1): 45–56. doi:10.1016/0012-365X(93)90052-U. 
    12. ^ a b c Simons, J.; de Weger, B. (2003). “Theoretical and computational bounds for m-cycles of the 3n + 1 problem”. Acta Arithmetica 117 (1): 51–70. Bibcode2005AcAri.117...51S. doi:10.4064/aa117-1-3. http://deweger.xs4all.nl/papers/%5B35%5DSidW-3n+1-ActaArith%5B2005%5D.pdf. 
    13. ^ Steiner, R. P. (1977). “A theorem on the syracuse problem”. Proceedings of the 7th Manitoba Conference on Numerical Mathematics. pp. 553–9. MR535032 
    14. ^ a b Simons, John L. (2005). “On the nonexistence of 2-cycles for the 3x+1 problem”. Math. Comp. 74: 1565–72. Bibcode2005MaCom..74.1565S. doi:10.1090/s0025-5718-04-01728-4. MR2137019. 
    15. ^ Terras, Riho (1976), “A stopping time problem on the positive integers”, Acta Arithmetica 30 (3): 241–252, doi:10.4064/aa-30-3-241-252, MR0568274, http://matwbn.icm.edu.pl/ksiazki/aa/aa30/aa3034.pdf 
    16. ^ Lagarias, Jeffrey (1990). “The set of rational cycles for the 3x+1 problem”. Acta Arithmetica 56 (1): 33–53. doi:10.4064/aa-56-1-33-53. ISSN 0065-1036. https://eudml.org/doc/206298. 
    17. ^ Marc Chamberland (2003). “Una actualització del problema 3x + 1” (イタリア語). Butlletí de la Societat Catalana de Matemàtiques 18 (1): 19–45. http://revistes.iec.cat/index.php/BSCM/article/view/9784/9778 2022年1月25日閲覧。. 
    18. ^ Marc Chamberland (2003年). “An Update on the 3x+1 Problem” (PDF). Marc Chamberland. 2022年2月21日閲覧。
    19. ^ Chamberland, Marc (1996). “A continuous extension of the 3x + 1 problem to the real line”. Dynam. Contin. Discrete Impuls Systems 2 (4): 495–509. 
    20. ^ Letherman, Simon; Schleicher, Dierk; Wood, Reg (1999). “The (3n + 1)-Problem and Holomorphic Dynamics”. Experimental Mathematics 8 (3): 241–252. doi:10.1080/10586458.1999.10504402. 
    21. ^ Scollo, Giuseppe (2007), “Looking for Class Records in the 3x+1 Problem by means of the COMETA Grid Infrastructure”, Grid Open Days at the University of Palermo, http://www.dmi.unict.it/~scollo/seminars/gridpa2007/CR3x+1paper.pdf 
    22. ^ Garner, Lynn E. (1981). “On the Collatz 3𝑛+1 algorithm” (英語). Proceedings of the American Mathematical Society 82 (1): 19–22. doi:10.1090/S0002-9939-1981-0603593-2. ISSN 0002-9939. https://www.ams.org/proc/1981-082-01/S0002-9939-1981-0603593-2/. 
    23. ^ [1]Theorem D.



    英和和英テキスト翻訳>> Weblio翻訳
    英語⇒日本語日本語⇒英語
      

    辞書ショートカット

    すべての辞書の索引

    「コラッツの問題」の関連用語











    コラッツの問題のお隣キーワード
    検索ランキング

       

    英語⇒日本語
    日本語⇒英語
       



    コラッツの問題のページの著作権
    Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

       
    ウィキペディアウィキペディア
    All text is available under the terms of the GNU Free Documentation License.
    この記事は、ウィキペディアのコラッツの問題 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

    ©2024 GRAS Group, Inc.RSS