コラッツの問題
1930年代ごろ、学生であったコラッツは数論的関数を有向グラフとして表現して、そのグラフの性質が関数のふるまいとどのように関連付けられるかに興味を持った。この時の彼のノートには、現在知られるものとは異なる関数について調べられている。コラッツはこれらの関数についての問題を出版することはなかったが、1950年の国際数学者会議をきっかけに広くこの問題が知られるようになり、1963年に初めて (1930年代にコラッツが研究していた形のものが) 紙面に取りあげられた。その後、この問題に興味を持った数学者によって研究される間に、様々な別名を得ることとなった。「ハッセのアルゴリズム」はヘルムート・ハッセに、「シラキュース問題」はシラキュース大学に、「角谷の問題」は角谷静夫に、「ウラムの問題」はスタニスワフ・ウラムに由来する。
3 3 2 0 + 3 2 2 2 + 3 1 2 3 + 3 0 2 6 2 7 − 3 4 = 151 47 {\displaystyle {\frac {3^{3}2^{0}+3^{2}2^{2}+3^{1}2^{3}+3^{0}2^{6}}{2^{7}-3^{4}}}={\frac {151}{47}}}
これは、下記の有理数のサイクルとなり、パリティは確かに (1 0 1 1 0 0 1) の周期となっていることがわかる。
151 47 → 250 47 → 125 47 → 211 47 → 340 47 → 170 47 → 85 47 → 151 47 {\displaystyle {\frac {151}{47}}\rightarrow {\frac {250}{47}}\rightarrow {\frac {125}{47}}\rightarrow {\frac {211}{47}}\rightarrow {\frac {340}{47}}\rightarrow {\frac {170}{47}}\rightarrow {\frac {85}{47}}\rightarrow {\frac {151}{47}}}
(1 0 1 1 0 0 1) の巡回置換は、上記の分数の1つに関連付けられる。例えば、サイクル (0 1 1 0 0 1 1) から同様の手順で有理数を得ると
例えば「任意の正の整数 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に到達する可能性は低くなると予想されることとも符合する。
コラッツの問題(コラッツのもんだい、Collatz problem)は、数論の未解決問題のひとつである。問題の結論の予想を指してコラッツ予想と言う。伝統的にローター・コラッツの名を冠されて呼ばれるが、固有名詞に依拠しない表現としては3n+1問題とも言われ、また初期にこの問題に取り組んだ研究者や場所の名を冠して、角谷の問題、米田の予想、ウラムの予想、シラキュース問題などとも呼ばれる。
数学者ポール・エルデシュは「数学はまだこの種の問題に対する用意ができていない」と述べた。また、ジェフリー・ラガリアスは2010年に、コラッツの予想は「非常に難しい問題であり、現代の数学では完全に手が届かない」と述べた。
2019年9月、テレンス・タオはコラッツの問題がほとんどすべての正の整数においてほとんど正しいとするプレプリントを発表し、論文は2022年5月に出版された。
この二つの予想を一般化して、「任意の正の整数 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を用いて3 (a ≥ 1) で表されるときには、上記のプロセスを繰り返せば、有限回数で1または3 (a ≥ 1) に到達することは予想される。a = 1の場合がコラッツの問題である。a = 2の場合は、上記でl = 2のケースである。
自明ではないサイクルの長さは少なくとも 17,087,915 である。Eliahouは1993年の論文で、サイクルの最小値が 2 を超えるならば、周期の長さ p が
p = 301994 a + 17087915 b + 85137581 c {\displaystyle p=301994a+17087915b+85137581c}
となることを示した。ここで a , b , c {\displaystyle a,b,c} は非負整数で、 b ≥ 1 {\displaystyle b\geq 1} かつ a c = 0 {\displaystyle ac=0} である。この結果は、 log  3 / log  2 {\displaystyle \log 3/\log 2} の 連分数展開と関連している。最新の検証では、2までコラッツ予想が正しいと判明しているので、同様の論法によりサイクルの長さの下限は114208327604 (「ショートカット」無しなら 186265759595) であると言える。