Collatz problem

ウィキペディア

コラッツの問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/04/15 15:46 UTC 版)

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

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

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

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

概要

1から9999までの数に対して、1にいたるまでのステップ数をグラフにしたもの。

1から10⁸までの、1に至るまでのステップ数のヒストグラム。x軸がステップ数で、頻度がy軸である。

2から10⁷までの、1にいたるまでのステップ数をグラフにしたもの。

ステップ数: 250, 1000, 4000, 20000, 100000, 500000までをそれぞれグラフ化したもの。

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

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

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

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

${\displaystyle f(n)={\begin{cases}n/2&{\mbox{if }}n\equiv 0\\3n+1&{\mbox{if }}n\equiv 1\end{cases}}{\pmod {2}}}$

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

• 各整数において1になるまでの回数はオンライン整数列大辞典の数列 A006577を，各整数に対する最大値はオンライン整数列大辞典の数列 A025586を参照。
• 「3を掛けて1を加えた後、奇数になるまで2で割る」という1回の作業で1となる数値は、1, 5, 21, 85, 341, ... と無限に存在する。

歴史

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

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

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

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

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

この予想を支持する論拠

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

経験的証拠

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

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

ヒューリスティクス

厳密な議論ではないヒューリスティクスであるが、ステップを経るごとに数の大きさがどのようになるかを考察する。今、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 は必ず偶数になることから、コラッツ写像の「ショートカット」形式が次の定義で与えられる：

${\displaystyle T(x)={\begin{cases}x/2&{\text{if }}x\equiv 0{\pmod {2}},\\(3x+1)/2&{\text{if }}x\equiv 1{\pmod {2}}.\end{cases}}}$

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

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

${\displaystyle R(n)={\begin{cases}\{2n\}&{\text{if }}n\equiv 0,1,2,3,5\\[4px]\left\{2n,{\frac {n-1}{3}}\right\}&{\text{if }}n\equiv 4\end{cases}}{\pmod {6}}.}$

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

コラッツ写像は、整数時に元々の定義と一致するように実数に拡張することができる。 これは補間関数と呼ばれる。 これを行うには、下記を満たす２つの関数を適当に決めればよい。

${\displaystyle g_{1}(n)={\begin{cases}1,&n{\text{ is even,}}\\0,&n{\text{ is odd,}}\end{cases}}}$

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

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

複素指数関数による定義でのジュリア集合。

複素関数で定義する方法は他にもたくさんある。たとえば、正弦関数と余弦関数の代わりに 複素指数関数を使用する方法がある：

${\displaystyle f(z)\triangleq {\frac {z}{2}}+{\frac {1}{4}}(2z+1)\left(1-e^{i\pi z}\right)}$

最初の1000個の数字の数列を示す有向グラフ。

x軸は初期値を表し、y軸は、1に至るまでの間での最大値を示す。このプロットでは、y軸の範囲を制限している：いくつかのxでは、途中の最大値が2.7×10⁷にもなる。(x = 9663の場合)

20ステップ未満のすべてのツリー。

参考文献

• Lagarias, Jeffrey C., ed (2010). The ultimate challenge: the 3x + 1 problem. Providence, R.I.: American Mathematical Society. ISBN 978-0-8218-4940-8. MR2663745. Zbl 1253.11003. https://books.google.co.jp/books?id=hekJ7JDMEVkC 

関連文献

• 『数学100の問題』 日本評論社 ISBN 978-4535606142 　「角谷の問題」として取り上げられている。
• 『数学の魔法の宝箱』 イアン・スチュアート (数学者) ソフトバンク クリエイティブ ISBN 978-4-7973-5982-4：「コラッツ＝シラキュース＝ウラム問題」として紹介されている。

関連項目

• タグシステム
• FRACTRAN

外部リンク

• Weisstein, Eric W. "Collatz Problem". mathworld.wolfram.com (英語).
• コラッツ予想 - ウェイバックマシン（2001年11月23日アーカイブ分） コラッツ予想計算
• コラッツ予想に関するプログラム集。　コラッツ予想計算、拡張問題にも対応可能。
• コラッツ問題のある一般化について (PDF) （2012年3月30日時点のアーカイブ）
• Collatz Conjecture コラッツの問題を検証する為の分散コンピューティング

脚注

[脚注の使い方]

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. ^ 数学Ⅱ・数学B（2011年1月24日時点のインターネットアーカイブ） (PDF) - 【センター試験】２０１１年度大学入試センター試験速報－問題と正解（47NEWS）（2011年1月23日時点のインターネットアーカイブ）
7. ^ “コラッツ予想 懸賞金1億2000万円”. Mathprize. Mathprize (2021年7月7日). 2022年1月21日時点のオリジナルよりアーカイブ。2022年2月21日閲覧。
8. ^ “数学者も恐れる「ハマると病む難問」 解けたら1億円、企業が懸賞金”. 朝日新聞デジタル. 朝日新聞社 (2021年9月24日). 2021年9月15日時点のオリジナルよりアーカイブ。2022年2月21日閲覧。
9. ^ Barina, David (2020). “Convergence verification of the Collatz problem”. The Journal of Supercomputing. doi:10.1007/s11227-020-03368-x. 
10. ^ 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. 
11. ^ ^{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. Bibcode: 2005AcAri.117...51S. doi:10.4064/aa117-1-3. http://deweger.xs4all.nl/papers/%5B35%5DSidW-3n+1-ActaArith%5B2005%5D.pdf. 
12. ^ Steiner, R. P. (1977). “A theorem on the syracuse problem”. Proceedings of the 7th Manitoba Conference on Numerical Mathematics. pp. 553–9. MR535032 
13. ^ ^{a b} Simons, John L. (2005). “On the nonexistence of 2-cycles for the 3x+1 problem”. Math. Comp. 74: 1565–72. Bibcode: 2005MaCom..74.1565S. doi:10.1090/s0025-5718-04-01728-4. MR2137019. 
14. ^ 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 
15. ^ コラッツ予想の変形について
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.