コラッツの問題

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

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

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

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

概要

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

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

2から10^7までの、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}}}$

任意の正の整数 n に対して、この関数 f (コラッツ写像とも呼ばれる) を繰り返し適用することで整数の無限列 {a_i}_{i ≧ 0}を得る。数式としての定義は次のようになる。

${\displaystyle a_{i}={\begin{cases}n&{\mbox{for }}i=0\\f(a_{i-1})&{\mbox{for }}i>0\end{cases}}}$

このとき、コラッツ予想を形式的に書くと、以下のようになる。

${\displaystyle \forall n\in \mathbb {N} ^{+}\ \exists i\in \mathbb {N} :(a_{0}=n\Rightarrow a_{i}=1)}$

すなわち、任意の正整数 n に対して f を繰り返し適用していると、f(f(…f(n)…)) = 1 がいつかは成り立つという主張がコラッツ予想である。1に到達して以降は、この数列は 1, 4, 2 を繰り返すのみとなるため、以降では最初に1に到達して以降の数は表記しないことにする。

コラッツ予想が誤りであるなら、1 を含まない数列を生成する初期値が存在するということになる。そのような数列は、1 を含まない繰り返し数列に突入するか、もしくは際限なく増大していくかのいずれかである。そのような数列はいまだ見つかっていない。

コンピュータを用いた計算により、2^68 までの初期値には反例がないことが確かめられている[6]。

例

• 初期値を 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 まで増大する。

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 (オンライン整数列大辞典の数列 A008884)

初期値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問に題材として取り上げられた[7]。

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万円を支払います」と発表した[8][9]。

この予想を支持する論拠

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

経験的証拠

この予想は、初期値が2^68 ≈ 2.95×10^20までは成り立つことがコンピュータで確認されている[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 は必ず偶数になることから、コラッツ写像の「ショートカット」形式が次の定義で与えられる：

${\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}}}$

コラッツ数列のサイクルとは相異なる正整数からなる数列 ${\displaystyle (a_{0},a_{1},\ldots ,a_{q})}$ であって、${\displaystyle T(a_{0})=a_{1}}$, ${\displaystyle T(a_{1})=a_{2}}$, ..., ${\displaystyle T(a_{q})=a_{0}}$ を満たすものである。唯一知られているサイクルは長さ2の ${\displaystyle (1,2)}$ で、これは自明なサイクルと呼ばれる。

サイクルの長さ

自明ではないサイクルの長さは少なくとも 17,087,915 である[11]。Eliahouは1993年の論文で、サイクルの最小値が 2^40 を超えるならば、周期の長さ p が

${\displaystyle p=301994a+17087915b+85137581c}$

となることを示した。ここで${\displaystyle a,b,c}$は非負整数で、${\displaystyle b\geq 1}$ かつ ${\displaystyle ac=0}$である。この結果は、${\displaystyle \log 3/\log 2}$の 連分数展開と関連している。最新の検証では、2^68までコラッツ予想が正しいと判明しているので、同様の論法によりサイクルの長さの下限は114208327604 (「ショートカット」無しなら 186265759595) であると言える。

k-サイクル

k-サイクルとは、奇数が連続する増加列 k 個と偶数が連続する減少列 k 個の 2k 個の部分で全体が構成されたサイクルである。例えばサイクルが、奇数による増加列1個と、偶数による減少列1個で構成されたなら、1-サイクルと呼ぶ[12]。Steiner (1977)は、1-サイクルが、自明なサイクル(1;2)のみであることを証明した[13][14]。ジョン・サイモンズ (John L. Simons) は、Steinerの方法を使って、2-サイクルが存在しないことを証明した[14]。サイモンズとde Wegerはこの証明を拡張して、k = 68 までの場合において、非自明なk-サイクルが存在しないことを示した[12]。また、k が69以上の場合においては、存在した場合のサイクルの最小値の範囲を与えた。例えば k = 69 の場合は、サイクルの最小値は 3.3389×10^17より大きく 6.4877×10^17より小さいことが示されている[12]。

コラッツ予想の他の形式

ボトムアップ方式

ボトムアップ方式で作成した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}}.}$

したがって、すべての正の整数が最終的に1になることを証明する代わりに、1がすべての正の整数に逆方向につながることを証明すればよい。 任意の整数n, n ≡ 1 (mod 2) ⇔ 3n + 1 ≡ 4 (mod 6) である。ゆえに、 n − 1/3 ≡ 1 (mod 2) ⇔ n ≡ 4 (mod 6)である。 推測的に、この逆関係は、1–2–4ループ（この記事の問題の説明のセクションで定義されている変更されていない関数fの4–2–1ループの逆）を除いてツリーを形成する。

操作3n + 1を、ショートカット操作3n + 1/2に置き換えた場合は、 コラッツグラフの定義は以下のようになる。

${\displaystyle 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 ≡ 2 (mod 3)。ゆえに、 2n − 1/3 ≡ 1 (mod 2) ⇔ n ≡ 2 (mod 3)である 。推測的に、この逆関係は、1–2ループ（上記のように修正された関数f（n）の1–2ループの逆）を除いてツリーを形成する。

パリティシーケンス（偶奇列）

本節では、コラッツ関数を少し変形したものを考える：

${\displaystyle 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のパリティシーケンス（もしくは、パリティベクトル）を、p_i = P(a_i), ただしa₀ = n, and a_i+1 = f(a_i) と定義する。 (3n + 1)/2 または n/2、どちらの操作が適用されるかは、パリティに依存する。パリティシーケンスはfによる操作の場合分けに等しい。 f(n)に対してこの形式を適用すると、２つの整数m とnのパリティシーケンスは、m とnが2^kを法として合同の場合のみ、最初のk項で一致するこが示される。これは、すべての整数がパリティシーケンスにより一意に識別されること意味し、さらに複数のコラッツ数列がある場合、対応するパリティシーケンスが異なる必要があることを意味する[1][15]。

n=a·2^k + b に関数 f を k 回適用すると、a·3^c + dとなる。ここでdはbに関数fをk回適用した結果で、cはその過程で3倍の演算を行った（増加した）回数である。（例えば、a·2^5 + 1 では、1が2,1,2,1と変化し最後に2になるので、3回の増加がある。よって結果はa·3^3+2 である。a·2^2 + 1 では、1が2に増加しその後1になるので、結果はa·3 + 1 となる。） bが2^k - 1の場合には、 k回の増加があり、結果は2·a·3^k - 1となる。aに掛かる係数は、aには無関係で、bにのみ依存する。これにより、特定の形式の数値が特定の反復回数の後、常により小さい数値になることを予測できます。例えば、4a + 1 は、2回のf操作により3a + 1となり、16a + 3は4回のf操作により9·a + 2となる。これらの小さくなった数が1へとつながるかどうかは、 aの値に依存する。

問題の拡張

整数全体への拡張

正整数だけではなく、負数も含む任意の整数から開始するコラッツ数列について考えることができる。このとき、自明なサイクル0→0を除いて、合計4つの既知のサイクルがあり、知られている限りでは任意の0でない整数は以下に示された4つのサイクルのいずれかに到達する。

以下の表において、奇数の値は太字で示されている。また各サイクルは、最小絶対値の要素を先頭にしている。

サイクル	奇数値のサイクル長	全サイクル長
1, 4, 2, 1 ...	1	3
−1, −2, −1 ...	1	2
−5, −14, −7, −20, −10, −5 ...	2	5
−17, −50, −25, −74, −37, −110, −55, −164, −82, −41, −122, −61, −182, −91, −272, −136, −68, −34, −17 ...	7	18

一般化されたコラッツの予想は、f による反復の下で、すべての整数が最終的に上記の4つのサイクルの1つ (または0→0の自明なサイクル) に入るという主張である。

分母が奇数である有理数への拡張

コラッツ写像は、分母が奇数である既約分数に拡張できる。ここで偶奇性の判定は分子の偶奇性によって判定し、それ以外は定義域が整数の場合と同様に行う。すなわち、分子が偶数であれば2で割り、奇数であればその有理数に3を掛けて1を足すこととする。「ショートカット」した定義を使用する場合、任意の周期的かつ既約なパリティ列は一意な有理数によって生成されることが知られている[16]。逆に、分母が奇数であるすべての有理数は、周期的なパリティ列を持っていると予想されている (周期性予想、periodicity conjecture[1])。

長さ n のパリティ列が奇数を正確に m 個含むとして、そのインデックスを k₀ < … < k_m−1 で表すとすると、パリティサイクルを生成する有理数が次のように決定される：

${\displaystyle {\frac {3^{m-1}2^{k_{0}}+\cdots +3^{0}2^{k_{m-1}}}{2^{n}-3^{m}}}}$

(1)

例えば、長さ7のパリティサイクル (1 0 1 1 0 0 1) は、0, 2, 3, 6 の位置にパリティ1 (すなわち奇数) が存在している。従って m = 4, k_i = 0, 2, 3, 6 (for 0 ≦ i ≦ 3) と置くと、周期列を生成する有理数が次のように求まる。

${\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) の周期となっていることがわかる。

${\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) から同様の手順で有理数を得ると

${\displaystyle {\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」への一般化を適用することによって得ることができる。

${\displaystyle 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-進整数環への拡張

有理数と類似の拡張として、コラッツ写像の2-進整数環 ${\displaystyle \mathbb {Z} _{2}}$ への拡張が挙げられる。この環は部分環として奇数分母の有理数全体からなる環を含んでいる。このとき写像は

$${\displaystyle 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}}}$$で与えられ、これは ${\displaystyle \mathbb {Z} _{2}}$ 上でwell-definedな連続写像であり、かつハール測度を保存する[17][18]。加えて、その力学系はエルゴードであることが知られている[1]。

実数・複素数への拡張

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

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

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

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

そしてこれらを使って下記のようにコラッツ写像を定義できる：

${\displaystyle f(x)\triangleq {\frac {x}{2}}\cdot g_{1}(x)\,+\,{\frac {3x+1}{2}}\cdot g_{2}(x)}$.

${\displaystyle g_{1}}$ と ${\displaystyle g_{2}}$ の選択肢として、例えば、 ${\displaystyle g_{1}(x)\triangleq \cos ^{2}\left({\tfrac {\pi }{2}}x\right)}$ と ${\displaystyle g_{2}(x)\triangleq \sin ^{2}\left({\tfrac {\pi }{2}}x\right)}$ を選ぶことができる。

実直線上でのこの写像の反復については、マーク・チェンバーランド (Marc Chamberland) の研究によると、この関数は実直線上に無限に多くの不動点を持ち、また反復合成について単調に無限大に発散する軌道も持つ[19]。

f(x) の正の不動点を小さい方から 0 < μ₁ < μ₂ < μ₃ < … とおく。このとき、[μ₁, μ₃] の範囲には周期アトラクターがちょうど2つ存在して、1つは {1, 2}、もう1つは {1.192531907..., 2.138656335...} である。

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

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

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

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

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

この場合異なるダイナミクスを示す。例えば ${\displaystyle \operatorname {Im} (z)\gg 1}$では、${\displaystyle f(z)\approx z+{\tfrac {1}{4}}}$となり発散する。 この定義に対応するジュリア集合は、右図のようになる。"haris"や"rays"と呼ばれる無数の構造がある。

検証計算の最適化

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

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

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

${\displaystyle {f^{k}}\left(a\ {2^{k}}+b\right)=a\ {3^{c\left(b\right)}}+d\left(b\right)}$.

c (もしくは 3^c)と d 配列は、k ビットの数すべてについて事前計算しておく。d(b) は b に f 関数を k 回行った数で、c(b) はその間に登場した奇数の数である[21]。例えば k = 5 なら5ステップのジャンプが可能で、そのために下位5ビットを分割して、下記配列を使う：

${\displaystyle c\left(0\dots 31\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\}}$

${\displaystyle d\left(0\dots 31\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\}}$

これは、2^k 個の事前計算とストレージが要求される。これにより計算速度が k 倍高速化出来るが、時間と空間のトレードオフである。

Modular restrictions

コラッツ予想の反例を探すにあたって、上記の事前計算を使うと加速させることができる。もし、与えられた b と k で、不等式

${\displaystyle {f^{k}}\left(a\ {2^{k}}+b\right)=a\ {3^{c\left(b\right)}}+d\left(b\right)<a\ {2^{k}}+b}$

が成り立ったとすると、すべての a についても成立する。そうすると、最初の反例（存在するとして）は、 2^k を法として b と合同ではないと言える[22]。

例えば、最初の反例は必ず奇数である。なぜならば f (2n) = n で、2n よりも小さいからである。同様に、最初の反例は mod 4 で3と合同である。なぜならば、f ^2(4n + 1) = 3n + 1 で、4n + 1 より小さいからである。コラッツ予想の反例でないすべての a には、上記不等式が成立する k が存在する。なので、ある数のコラッツ予想の検証するとき、合同なクラスを検証するとよい。k が増加したときの検証は、より小さい k で除外されなかった b についてのみ検証すればよい。指数関数的に小さい割合だけが残ることになる[23]。例えば mod 32 では、b = 7, 15, 27, 31 だけが残る。

類似の問題

関数 f の定義を少し変えることにより、コラッツの問題の類似を考えることができる。

変数nが奇数の時の乗数の奇数一般への拡張による類似問題

例えば「任意の正の整数 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 が偶数の場合、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を用いて3^a–1 (a ≥ 1) で表されるときには、上記のプロセスを繰り返せば、有限回数で1または3^a–1 (a ≥ 1) に到達することは予想される。a = 1の場合がコラッツの問題である。a = 2の場合は、上記でl = 2のケースである。

変数nが奇数の時の乗数と加算数双方の、奇数一般への拡張による類似問題

以上のことから、一般化は困難ではあるが、個別に考えるなら、さらに進んで、「任意の正の整数 n に対して

• n が偶数の場合、n を 2 で割る
• n が奇数の場合、n に 2m – 1 (m ≥ 1) をかけて、2l – 1 (l ≥ 1) を足す

という操作を繰り返すとき、n、m、lの値に応じてどのような数列が展開されるか」

という問題にも拡張できるなど、コラッツの問題の類似問題の幅は広い。

ギャラリー

• 
  最初の1000個の数字の数列を示す有向グラフ。
• 
  x軸は初期値を表し、y軸は、1に至るまでの間での最大値を示す。このプロットでは、y軸の範囲を制限している：いくつかのxでは、途中の最大値が2.7×10^7にもなる。(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. ^ 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. ^ “Almost all orbits of the Collatz map attain almost bounded values”. arXiv (2019年9月8日). 2021年10月15日閲覧。
4. ^ 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) - 【センター試験】２０１１年度大学入試センター試験速報－問題と正解（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. ^ 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. 
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. ^ 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. 
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.