コラッツの問題

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

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

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

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

概要

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

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

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

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

任意の正の整数 テンプレート:Mvar に対して、以下で定められる操作について考える。

• テンプレート:Mvar が偶数の場合、テンプレート:Mvar を 2 で割る
• テンプレート:Mvar が奇数の場合、テンプレート:Mvar に 3 を掛けて 1 を足す

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

モジュラ計算の表記を用いて、上記の操作を関数 テンプレート:Mvar として定義する。

$f(n)=\{\begin{array}{cc}n/2& \text{if }n\equiv 0\\ 3n+1& \text{if }n\equiv 1\end{array}(\mathrm{mod}2)$

任意の正の整数 テンプレート:Mvar に対して、この関数 テンプレート:Mvar (コラッツ写像とも呼ばれる) を繰り返し適用することで整数の無限列 テンプレート:Mathを得る。数式としての定義は次のようになる。

$a_i=\{\begin{array}{cc}n& \text{for }i=0\\ f(a_{i-1})& \text{for }i>0\end{array}$

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

$\mathrm{\forall }n\in {\mathbb{N}}^{+}\mathrm{\exists }i\in \mathbb{N}:(a_0=n\Rightarrow a_i=1)$

すなわち、任意の正整数 テンプレート:Mvar に対して テンプレート:Mvar を繰り返し適用していると、テンプレート:Math がいつかは成り立つという主張がコラッツ予想である。1に到達して以降は、この数列は 1, 4, 2 を繰り返すのみとなるため、以降では最初に1に到達して以降の数は表記しないことにする。

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

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

例

• 初期値を 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のときの テンプレート:Math の値のグラフ

• 各整数において1になるまでの回数はテンプレート:OEISを，各整数に対する最大値はテンプレート:OEISを参照。
• 「3を掛けて1を加えた後、奇数になるまで2で割る」という1回の作業で1となる数値は、テンプレート:数列 と無限に存在する。

歴史

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

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

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

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

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

この予想を支持する論拠

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

経験的証拠

この予想は、初期値が2⁶⁸ ≈ 2.95×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に平均収束するということであり、厳密には予想の確からしさとは無関係である。テンプレート:要出典範囲

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

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

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

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

サイクル

テンプレート:Mvar が奇数であるときに テンプレート:Math は必ず偶数になることから、コラッツ写像の「ショートカット」形式が次の定義で与えられる：

$T(x)=\{\begin{array}{cc}x/2& \text{if }x\equiv 0(\mathrm{mod}2),\\ (3x+1)/2& \text{if }x\equiv 1(\mathrm{mod}2).\end{array}$

コラッツ数列のサイクルとは相異なる正整数からなる数列 テンプレート:Nowrap であって、$T(a_0)=a_1$, $T(a_1)=a_2$, ..., $T(a_q)=a_0$ を満たすものである。唯一知られているサイクルは長さ2の $(1,2)$ で、これは自明なサイクルと呼ばれる。

サイクルの長さ

自明ではないサイクルの長さは少なくとも テンプレート:Val である。Eliahouは1993年の論文で、サイクルの最小値が テンプレート:Math を超えるならば、周期の長さ テンプレート:Mvar が

$p=301994a+17087915b+85137581c$

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

k-サイクル

テンプレート:Mvar-サイクルとは、奇数が連続する増加列 テンプレート:Mvar 個と偶数が連続する減少列 テンプレート:Mvar 個の テンプレート:Math 個の部分で全体が構成されたサイクルである。例えばサイクルが、奇数による増加列1個と、偶数による減少列1個で構成されたなら、1-サイクルと呼ぶ。Steiner (1977)は、1-サイクルが、自明なサイクル(1;2)のみであることを証明した。ジョン・サイモンズテンプレート:Smallは、Steinerの方法を使って、2-サイクルが存在しないことを証明した。サイモンズとde Wegerはこの証明を拡張して、テンプレート:Math までの場合において、非自明なテンプレート:Mvar-サイクルが存在しないことを示した。また、テンプレート:Mvar が69以上の場合においては、存在した場合のサイクルの最小値の範囲を与えた。例えば テンプレート:Math の場合は、サイクルの最小値は テンプレート:Valより大きく テンプレート:Valより小さいことが示されている。

コラッツ予想の他の形式

ボトムアップ方式

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

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

$R(n)=\{\begin{array}{cc}\{2n\}& \text{if }n\equiv 0,1,2,3,5\\ [4px]\{2n,\frac{n-1}{3}\}& \text{if }n\equiv 4\end{array}(\mathrm{mod}6).$

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

操作テンプレート:Mathを、ショートカット操作テンプレート:Mathに置き換えた場合は、 コラッツグラフの定義は以下のようになる。

$R(n)=\{\begin{array}{cc}\{2n\}& \text{if }n\equiv 0,1\\ [4px]\{2n,\frac{2n-1}{3}\}& \text{if }n\equiv 2\end{array}(\mathrm{mod}3).$

任意の整数テンプレート:Mvar, テンプレート:Math ⇔ テンプレート:Math。ゆえに、 テンプレート:Math ⇔ テンプレート:Mathである 。推測的に、この逆関係は、1–2ループ（上記のように修正された関数f（n）の1–2ループの逆）を除いてツリーを形成する。

剰余列

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

$f(n)=\{\begin{array}{cc}n/2& \text{if }n\equiv 0\\ (3n+1)/2& \text{if }n\equiv 1\end{array}(\mathrm{mod}2).$

nが奇数の場合には3n + 1が必ず偶数になるので上記のようにできる。

テンプレート:Mathをxの2で割った余りとする。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項で一致するこが示される。これは、すべての整数が剰余列により一意に識別されること意味し、さらに複数のコラッツ数列がある場合、対応する剰余列が異なる必要があることを意味する。

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

法の一般化

本節ではショートカット版を、たんにコラッツ写像と称する。

テンプレート:Mvarを2以上の整数として

${\rho }_{\alpha }(x)=[0,\alpha )\cap (x+\alpha \mathbb{Z})$

という、各整数にテンプレート:Mvarを法とした非負の最小の余りを返す関数を導入すると、コラッツ写像はテンプレート:Mathと書ける。このことから、

$T_{\alpha }(x)=\frac{({\rho }_{\alpha }(x)+{\rho }_{\alpha }(-x)+1)x+{\rho }_{\alpha }(-x)}{\alpha }$

と定めると、法テンプレート:Mvarについて一般化されたコラッツ写像テンプレート:Mvarが得られる。 この写像は以下の特徴を持つ。

• テンプレート:Math.
• テンプレート:Math.
• テンプレート:Math.

したがって、とくに1の周期軌道と、整数上の不動点の分布が、どのテンプレート:Mvarに於いてもオリジナルのコラッツ写像と酷似する。これらの周期軌道を自明な軌道と呼ぶことにすると、既に10未満のテンプレート:Mvarに於いては、テンプレート:Mathに於いて、正の範囲に非自明な周期軌道が確認されている。このことから次の命題が興味の対象となる。 テンプレート:Quotation "そのような法すべて"からなる集合に2が含まれるか? がオリジナルのコラッツの問題に相当する。

定義域の拡張

整数全体への拡張

正整数だけではなく、負数も含む任意の整数から開始するコラッツ数列について考えることができる。このとき、自明なサイクル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

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

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

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

長さ テンプレート:Mvar のパリティ列が奇数を正確に テンプレート:Mvar 個含むとして、そのインデックスを テンプレート:Math で表すとすると、パリティサイクルを生成する有理数が次のように決定される：

例えば、長さ7のパリティサイクル テンプレート:Nowrap は、0, 2, 3, 6 の位置にパリティ1 (すなわち奇数) が存在している。従って テンプレート:Math, テンプレート:Math と置くと、周期列を生成する有理数が次のように求まる。

$\frac{3^3{2}^0+3^2{2}^2+3^1{2}^3+3^0{2}^6}{2^7-3^4}=\frac{151}{47}$

これは、下記の有理数のサイクルとなり、パリティは確かに テンプレート:Nowrap の周期となっていることがわかる。

$\frac{151}{47}\to \frac{250}{47}\to \frac{125}{47}\to \frac{211}{47}\to \frac{340}{47}\to \frac{170}{47}\to \frac{85}{47}\to \frac{151}{47}$

テンプレート:Nowrap の巡回置換は、上記の分数の1つに関連付けられる。例えば、サイクル テンプレート:Nowrap から同様の手順で有理数を得ると

$\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番目に対応している。

コラッツ予想が正しいことを仮定すると、テンプレート:Nowrap と テンプレート:Nowrap が正の整数（それぞれ1と2）によって生成される唯一のパリティサイクルであることが示される。

有理数の分母が3の倍数でない場合、この拡張されたコラッツ数列はすべて同じ分母を持ち、このとき分子の列はコラッツ関数の「テンプレート:Math」への一般化を適用することによって得ることができる。

$T_d(x)=\{\begin{array}{cc}\frac{x}{2}& \text{if }x\equiv 0(\mathrm{mod}2),\\ [4px]\frac{3x+d}{2}& \text{if }x\equiv 1(\mathrm{mod}2).\end{array}$

2-進整数環への拡張

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

$$T(x)=\{\begin{array}{cc}\frac{x}{2}& \text{if}x\equiv 0mod2\\ \frac{3x+1}{2}& \text{if}x\equiv 1mod2\end{array}$$で与えられ、これは ${\mathbb{Z}}_2$ 上でwell-definedな連続写像であり、かつハール測度を保存する。加えて、その力学系はエルゴードであることが知られている。

実数・複素数への拡張

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

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

$g_1(n)=\{\begin{array}{cc}1,& n\text{ is even,}\\ 0,& n\text{ is odd,}\end{array}$

$g_2(n)=\{\begin{array}{cc}0,& n\text{ is even,}\\ 1,& n\text{ is odd,}\end{array}$

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

$f(x)\triangleq \frac{x}{2}\cdot g_1(x)+\frac{3x+1}{2}\cdot g_2(x)$.

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

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

テンプレート:Math の正の不動点を小さい方から テンプレート:Math とおく。このとき、テンプレート:Math の範囲には周期アトラクターがちょうど2つ存在して、1つは テンプレート:Math、もう1つは テンプレート:Mathである。

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

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

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

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

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

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

検証計算の最適化

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

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

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

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

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

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

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

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

剰余類による制限

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

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

が成り立ったとすると、すべての テンプレート:Math についても成立する。そうすると、最初の反例（存在するとして）は、 テンプレート:Math を法として テンプレート:Math と合同ではないと言える。

例えば、最初の反例は必ず奇数である。なぜならば テンプレート:Math で、テンプレート:Math よりも小さいからである。同様に、最初の反例は テンプレート:Math で3と合同である。なぜならば、テンプレート:Math で、テンプレート:Math より小さいからである。コラッツ予想の反例でないすべての テンプレート:Math には、上記不等式が成立する テンプレート:Math が存在する。なので、ある数のコラッツ予想の検証するとき、合同なクラスを検証するとよい。テンプレート:Math が増加したときの検証は、より小さい テンプレート:Math で除外されなかった テンプレート:Math についてのみ検証すればよい。指数関数的に小さい割合だけが残ることになるテンプレート:Refnest。例えば テンプレート:Math では、テンプレート:Math だけが残る。

類似の問題

関数 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個の数字の数列を示す有向グラフ。
• 
  テンプレート:Mvar軸は初期値を表し、テンプレート:Mvar軸は、1に至るまでの間での最大値を示す。このプロットでは、テンプレート:Mvar軸の範囲を制限している：いくつかのテンプレート:Mvarでは、途中の最大値がテンプレート:Valにもなる。(テンプレート:Mathの場合)
• 
  20ステップ未満のすべてのツリー。

参考文献

• テンプレート:Cite book

関連文献

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

関連項目

• タグシステム
• FRACTRAN

外部リンク

• テンプレート:MathWorld
• テンプレート:Wayback コラッツ予想計算
• コラッツ予想に関するプログラム集。　コラッツ予想計算、拡張問題にも対応可能。
• テンプレート:PDFlink（2012年3月30日時点のアーカイブ）
• Collatz Conjecture コラッツの問題を検証する為の分散コンピューティング