コラッツの問題
コラッツの問題(コラッツのもんだい、Collatz problem)は、数論の未解決問題のひとつである。問題の結論の予想を指してコラッツ予想と言う。伝統的にローター・コラッツの名を冠されて呼ばれるが、固有名詞に依拠しない表現としては3n+1問題とも言われ、また初期にこの問題に取り組んだ研究者の名を冠して、角谷の問題、米田の予想、ウラムの予想、シラキュース問題などとも呼ばれる。
数学者ポール・エルデシュは「数学はまだこの種の問題に対する用意ができていない」と述べた。また、ジェフリー・ラガリアスは2010年に、コラッツの予想は「非常に難しい問題であり、現代の数学では完全に手が届かない」と述べた。
2019年12月、テレンス・タオはコラッツの問題がほとんどすべての正の整数においてほとんど正しいとする論文を発表した。
任意の正の整数 n に対して、以下で定められる操作について考える。
n が偶数の場合、n を 2 で割る
n が奇数の場合、n に 3 をかけて 1 を足す
このとき、「どんな初期値から始めても、有限回の操作のうちに必ず 1 に到達する(そして 1→4→2→1 というループに入る)」という主張が、コラッツの予想である。
モジュラ計算の表記を用いて、上記の操作を関数 f として定義する。
f(n) = \begin{cases} n/2 &\mbox{if } n \equiv 0 \\ 3n+1 & \mbox{if } n\equiv 1 \end{cases} \pmod{2}
任意の正の整数 n に対して、この関数 f (コラッツ写像とも呼ばれる) を繰り返し適用することで整数の無限列 {ai}i ≧ 0を得る。数式としての定義は次のようになる。
a_i = \begin{cases}n & \mbox{for } i = 0 \\ f(a_{i-1}) & \mbox{for } i > 0\end{cases}
このとき、コラッツ予想を形式的に書くと、以下のようになる。
\forall n \isin \mathbb{N} > 0 \ \exists i \isin \mathbb{N}: (a_0 = n \Rightarrow a_i = 1)
すなわち、任意の正整数 n に対して f を繰り返し適用していると、f(f(…f(n)…)) = 1 がいつかは成り立つという主張がコラッツ予想である。1に到達して以降は、この数列は 1, 4, 2 を繰り返すのみとなるため、以降では最初に1に到達して以降の数は表記しないことにする。
コラッツ予想が誤りであるなら、1 を含まない数列を生成する初期値が存在するということになる。そのような数列は、1 を含まない繰り返し数列に突入するか、もしくは際限なく増大していくかのいずれかである。そのような数列はいまだ見つかっていない。
コンピュータを用いた計算により、268 までの初期値には反例がないことが確かめられている。
初期値を 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 を選ぶと、以下のように数列の項数は112にまで及び、その値は最終的に 1 に到達する前に最大 9232 まで増大する。
1930年代ごろ、学生であったコラッツは数論的関数を有向グラフとして表現して、そのグラフの性質が関数のふるまいとどのように関連付けられるかに興味を持った。この時の彼のノートには、現在知られるものとは異なる関数について調べられている。コラッツはこれらの関数についての問題を出版することはなかったが、1950年の国際数学者会議をきっかけに広くこの問題が知られるようになり、1963年に初めて (1930年代にコラッツが研究していた形のものが) 紙面に取りあげられた。その後、この問題に興味を持った数学者によって研究される間に、様々な別名を得ることとなった。「ハッセのアルゴリズム」はヘルムート・ハッセに、「シラキュース問題」はシラキュース大学に、「角谷の問題」は角谷静夫に、「ウラムの問題」はスタニスワフ・ウラムに由来する。
コラッツ予想の解決にはいくつかの懸賞金がかけられており、コクセターが50ドル、エルデシュが500ドル、ブライアン・スウェイツBryan Thwaitesは1000ポンドを申し出ている。
2011年度大学入試センター試験数学IIB第6問に題材として取り上げられた。
2019年、テレンス・タオは「limN→∞ f(N) = +∞ を満たす任意の関数 f : ℕ+ → ℝ について、N から始まるコラッツ数列の最小値は (Logarithmic densityの意味で) ほとんど全ての自然数 N において f(N) より小さい」ことを証明し、コラッツ予想は「『ほとんど』全ての自然数で『ほとんど』正しい」ことが示された。帰結として例えば、N から始まるコラッツ数列の最小値はほとんど全ての自然数 N において log log log log N より小さくなることが従う。
2021年7月7日、株式会社音圧爆上げくんが、「コラッツ予想の真偽を明らかにした方に懸賞金1億2000万円を支払います」と発表した。
コラッツの予想は未解決だが、この問題を研究した多くの数学者は正しいだろうと考えている。そう予想される理由を以下に挙げる。
この予想は、初期値が268 ≈ 2.95×1020までは成り立つことがコンピュータで確認されている。この数値は、コンピュータのスピードアップとテスト技術の向上に伴って更新され続けている。
しかしこういったコンピューターでの検証は、予想が真であるという証拠にはならない。ポリア予想、メルテンス予想、スキューズ数の場合に示されているように、非常に大きな数において予想の反例が見つかることがある。
厳密な議論ではないヒューリスティクスであるが、ステップを経るごとに数の大きさがどのようになるかを考察する。今、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 は必ず偶数になることから、コラッツ写像の「ショートカット」形式が次の定義で与えられる:
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}
コラッツ数列のサイクルとは相異なる正整数からなる数列 (a_0, a_1, \ldots, a_q) であって、T(a_0)=a_1, T(a_1)=a_2, ..., T(a_q)=a_0 を満たすものである。唯一知られているサイクルは長さ2の (1,2) で、これは自明なサイクルと呼ばれる。
自明ではないサイクルの長さは少なくとも 17087915 である。Eliahouは1993年の論文で、サイクルの最小値が 240 を超えるならば、周期の長さ p が
p = 301994 a + 17087915 b + 85137581 c
となることを示した。ここでa,b,cは非負整数で、b \geq 1 かつ  ac=0である。この結果は、\log 3 / \log 2の 連分数展開と関連している。最新の検証では、268までコラッツ予想が正しいと判明しているので、同様の論法によりサイクルの長さの下限は114208327604 (「ショートカット」無しなら 186265759595) であると言える。
k-サイクルとは、奇数が連続する増加列 k 個と偶数が連続する減少列 k 個の 2k 個の部分で全体が構成されたサイクルである。例えばサイクルが、奇数による増加列1個と、偶数による減少列1個で構成されたなら、1-サイクルと呼ぶ。Steiner (1977)は、1-サイクルが、自明なサイクル(1;2)のみであることを証明した。ジョン・サイモンズ (John L. Simons) は、Steinerの方法を使って、2-サイクルが存在しないことを証明した。サイモンズとde Wegerはこの証明を拡張して、k = 68 までの場合において、非自明なk-サイクルが存在しないことを示した。また、k が69以上の場合においては、存在した場合のサイクルの最小値の範囲を与えた。例えば k = 69 の場合は、サイクルの最小値は 3.3389より大きく 6.4877より小さいことが示されている。
別のアプローチをとってみる:ボトムアップ方式でいわゆるコラッツグラフを作成してみる。
コラッツグラフは、以下のように操作を逆にして定義する。
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.
したがって、すべての正の整数が最終的に1になることを証明する代わりに、1がすべての正の整数に逆方向につながることを証明すればよい。
任意の整数n, n ≡ 1 (mod 2) ⇔ 3n + 1 ≡ 4 (mod 6) である。ゆえに、
n − 1 ≡ 1 (mod 2) ⇔ n ≡ 4 (mod 6)である。
推測的に、この逆関係は、1–2–4ループ(この記事の問題の説明のセクションで定義されている変更されていない関数fの4–2–1ループの逆)を除いてツリーを形成する。
操作3n + 1を、ショートカット操作3n + 1に置き換えた場合は、
コラッツグラフの定義は以下のようになる。
R(n) = \begin{cases} \{2n\} & \text{if } n\equiv 0,1 \\[4px] \left\{2n,\frac{2n-1}{3}\right\} & \text{if } n\equiv 2 \end{cases} \pmod 3.
任意の整数n, n ≡ 1 (mod 2) ⇔ 3n + 1 ≡ 2 (mod 3)。ゆえに、
2n − 1 ≡ 1 (mod 2) ⇔ n ≡ 2 (mod 3)である 。推測的に、この逆関係は、1–2ループ(上記のように修正された関数f(n)の1–2ループの逆)を除いてツリーを形成する。
本節では、コラッツ関数を少し変形したものを考える:
f(n) = \begin{cases} n/2 &\text{if } n \equiv 0 \\ (3n +1)/2 & \text{if } n \equiv 1 \end{cases} \pmod{2}.
nが奇数の場合には3n + 1が必ず偶数になるので上記のようにできる。
P(…)をパリティ数とする。P(2n) = 0 で、P(2n + 1) = 1 である。整数nのパリティシーケンス(もしくは、パリティベクトル)を、pi = P(ai), ただしa0 = n, and ai+1 = f(ai)
と定義する。
(3n + 1)/2 または n/2、どちらの操作が適用されるかは、パリティに依存する。パリティシーケンスはfによる操作の場合分けに等しい。
f(n)に対してこの形式を適用すると、2つの整数m とnのパリティシーケンスは、m とnが2kを法として合同の場合のみ、最初のk項で一致するこが示される。これは、すべての整数がパリティシーケンスにより一意に識別されること意味し、さらに複数のコラッツ数列がある場合、対応するパリティシーケンスが異なる必要があることを意味する。
n=a·2k + b に関数 f を k 回適用すると、a·3c + dとなる。ここでdはbに関数fをk回適用した結果で、cはその過程で3倍の演算を行った(増加した)回数である。(例えば、a·25 + 1 では、1が2,1,2,1と変化し最後に2になるので、3回の増加がある。よって結果はa·33+2 である。a·22 + 1 では、1が2に増加しその後1になるので、結果はa·3 + 1 となる。) bが2k - 1の場合には、 k回の増加があり、結果は2·a·3k - 1となる。aに掛かる係数は、aには無関係で、bにのみ依存する。これにより、特定の形式の数値が特定の反復回数の後、常により小さい数値になることを予測できます。例えば、4a + 1 は、2回のf操作により3a + 1となり、16a + 3は4回のf操作により9·a + 2となる。これらの小さくなった数が1へとつながるかどうかは、 aの値に依存する。
正整数だけではなく、負数も含む任意の整数から開始するコラッツ数列について考えることができる。このとき、自明なサイクル0→0を除いて、合計4つの既知のサイクルがあり、知られている限りでは任意の0でない整数は以下に示された4つのサイクルのいずれかに到達する。
以下の表において、奇数の値は太字で示されている。また各サイクルは、最小絶対値の要素を先頭にしている。
一般化されたコラッツの予想は、f による反復の下で、すべての整数が最終的に上記の4つのサイクルの1つ (または0→0の自明なサイクル) に入るという主張である。
コラッツ写像は、分母が奇数である既約分数に拡張できる。ここで偶奇性の判定は分子の偶奇性によって判定し、それ以外は定義域が整数の場合と同様に行う。すなわち、分子が偶数であれば2で割り、奇数であればその有理数に3を掛けて1を足すこととする。「ショートカット」した定義を使用する場合、任意の周期的かつ既約なパリティ列は一意な有理数によって生成されることが知られている。逆に、分母が奇数であるすべての有理数は、周期的なパリティ列を持っていると予想されている (周期性予想、periodicity conjecture)。
長さ n のパリティ列が奇数を正確に m 個含むとして、そのインデックスを k0 < … < km−1 で表すとすると、パリティサイクルを生成する有理数が次のように決定される:
例えば、長さ7のパリティサイクル (1 0 1 1 0 0 1) は、0, 2, 3, 6 の位置にパリティ1 (すなわち奇数) が存在している。従って m = 4, ki = 0, 2, 3, 6 (for 0 ≦ i ≦ 3) と置くと、周期列を生成する有理数が次のように求まる。
\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) の周期となっていることがわかる。
\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) から同様の手順で有理数を得ると
\frac{3^3 2^1 + 3^2 2^2 + 3^1 2^5 + 3^0 2^6}{2^7 - 3^4} = \frac{250}{47}
となり、先の例で得たサイクルの2番目に対応している。
コラッツ予想が正しいことを仮定すると、(1 0) と (0 1) が正の整数(それぞれ1と2)によって生成される唯一のパリティサイクルであることが示される。
有理数の分母が3の倍数でない場合、この拡張されたコラッツ数列はすべて同じ分母を持ち、このとき分子の列はコラッツ関数の「3n + d」への一般化を適用することによって得ることができる。
T_d(x) = \begin{cases} \frac{x}{2} &\text{if } x \equiv 0 \pmod{2},\\[4px] \frac{3x+d}{2} & \text{if } x\equiv 1 \pmod{2}. \end{cases}
有理数と類似の拡張として、コラッツ写像の2-進整数環 \mathbb{Z}_2 への拡張が挙げられる。この環は部分環として奇数分母の有理数全体からなる環を含んでいる。このとき写像は
T(x)=
\begin{cases}
\frac{x}{2} &\textrm{if}\ x\equiv 0\mod 2\\
\frac{3x+1}{2} &\textrm{if}\ x\equiv 1\mod 2
\end{cases}で与えられ、これは \mathbb{Z}_2 上でwell-definedな連続写像であり、かつハール測度を保存する。加えて、その力学系はエルゴードであることが知られている。
コラッツ写像は、次の式で定義される滑らかな関数を整数に制限したものと見なせる:
f(x)=\frac 1 2 x \cos^2\left(\frac \pi 2 x\right)+\frac {3x+1} {2} \sin^2\left(\frac \pi 2 x\right)
実直線上でのこの写像の反復については、マーク・チェンバーランド (Marc Chamberland) の研究によると、この関数は実直線上に無限に多くの不動点を持ち、また反復合成について単調に無限大に発散する軌道も持つ。
f(x) の正の不動点を小さい方から 0 < μ1 < μ2 < μ3 < … とおく。このとき、[μ1, μ3] の範囲には周期アトラクターがちょうど2つ存在して、1つは {1, 2}、もう1つは {1.192531907..., 2.138656335...} である。
Letherman, Schleicher および Wood はこの関数の研究を複素平面へと拡張した。ほとんどの複素平面上の点は無限遠へと発散するが、境界となるジュリア集合はフラクタル図形を描く。
上記の パリティシーケンス により、コラッツ数列の計算の高速化が可能である。
(パリティシーケンス節の f 関数を使ったとして)k ステップ先にジャンプするために、まず現在の数値を2つに分割する: b(2進数表記で下位 k ビット)と、a(残りの上位ビット)。k ステップをジャンプした結果は以下になる:
{f^k}\left(a\ {2^k}+b\right)=a\ {3^{c\left(b\right)}+d\left(b\right).
c (もしくは 3c)と d 配列は、k ビットの数すべてについて事前計算しておく。d(b) は b に f 関数を k 回行った数で、c(b) はその間に登場した奇数の数である。例えば k  5 なら5ステップのジャンプが可能で、そのために下位5ビットを分割して、下記配列を使う:
c\left(0\dots31\right)=\left\{0,3,2,2,2,2,2,4,1,4,1,3,2,2,3,4,1,2,3,3,1,1,3,3,2,3,2,4,3,3,4,5\right\}
d\left(0\dots31\right)=\left\{0,2,1,1,2,2,2,20,1,26,1,10,4,4,13,40,2,5,17,17,2,2,20,20,8,22,8,71,26,26,80,242\right\}
これは、2k 個の事前計算とストレージが要求される。これにより計算速度が k 倍高速化出来るが、時間と空間のトレードオフである。
コラッツ予想の反例を探すにあたって、上記の事前計算を使うと加速させることができる。もし、与えられた b と k で、不等式
{f^k}\left(a\ {2^k}+b\right)=a\ {3^{c\left(b\right)}+d\left(b\right)<a\ {2^k}+b
が成り立ったとすると、すべての a についても成立する。そうすると、最初の反例(存在するとして)は、 2k を法として b と合同ではないと言える。
例えば、最初の反例は必ず奇数である。なぜならば f (2n)  n で、2n よりも小さいからである。同様に、最初の反例は mod 4 で3と合同である。なぜならば、f 2(4n + 1)  3n + 1 で、4n + 1 より小さいからである。コラッツ予想の反例でないすべての a には、上記不等式が成立する k が存在する。なので、ある数のコラッツ予想の検証するとき、合同なクラスを検証するとよい。k  が増加したときの検証は、より小さい k で除外されなかった b についてのみ検証すればよい。指数関数的に小さい割合だけが残ることになる。例えば mod 32 では、b  7, 15, 27, 31 だけが残る。
関数 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の値に応じてどのような数列が展開されるか」
という問題にも拡張できるなど、コラッツの問題の類似問題の幅は広い。