Collatz予想
概要
Collatz予想（Collatz conjecture）とは、正の整数に「偶数なら $2$ で割り、奇数なら $3$ 倍して $1$ を足す」操作を繰り返すと、どの数から始めても必ず $1$ に到達するという予想で、$3x+1$ 問題、角谷の問題などとも呼ばれ、2025 年の時点で未解決である。最初の $k$ 回の偶奇の並びは $n$ を $2^k$ で割った余りと 1 対 1 に対応し、これからほとんどすべての $n$ で軌道が $n$ を下回ることが証明できる。$1$ を含まない周期軌道があれば $\log_23$ の非常によい有理数近似が得られるので、非常に長くなければならない。Tao は、対数密度の意味でほとんどすべての軌道の最小値が、無限大に発散する任意の関数より小さいことを示した。
前提知識: 合同式, 数学的帰納法, 二項分布, Chebyshevの不等式
Collatz予想（Collatz conjecture）とは、正の整数 $n$ に「偶数なら $2$ で割り、奇数なら $3$ 倍して $1$ を足す」という操作を繰り返すと、どの $n$ から始めても必ず $1$ に到達する、という予想である。$3x+1$ 予想、$3x+1$ 問題とも呼ばれ、Syracuse 問題、Hasse のアルゴリズム、Ulam の問題のほか、角谷静夫（Shizuo Kakutani）の名で角谷の問題とも呼ばれる（Lag21 §1, p. 1）。操作は小学生にも分かるが、予想は 2025 年の時点で未解決である（Bar25 p. 2）。$2^{71}$ までのすべての開始値については、計算機で確かめられている（Bar25 p. 1）。
この記事では、予想を正確に述べ、同値な言い換えを示す。そのうえで、最初の $k$ 回の偶奇の並びが $n$ を $2^k$ で割った余りと 1 対 1 に対応するという定理（thm-clz-parity）を証明し、それを使って「ほとんどすべての $n$ で、軌道はいつか $n$ より小さくなる」という定理（thm-clz-terras）を完全に証明する。さらに、$1$ を含まない周期軌道がもしあれば満たすべき不等式（thm-clz-cycle）を証明する。Tao の定理などの深い結果は、主張だけを述べる。
定義と予想
正の整数の全体を $\mathbb{N}_{>0}$ と書く。$C,T\colon\mathbb{N}_{>0}\to\mathbb{N}_{>0}$ を
$$
C(n)=\begin{cases}3n+1&(n\text{ が奇数})\\ n/2&(n\text{ が偶数})\end{cases}\qquad
T(n)=\begin{cases}(3n+1)/2&(n\text{ が奇数})\\ n/2&(n\text{ が偶数})\end{cases}
$$
で定める。$C$ を Collatz 写像、$T$ を $3x+1$ 写像という。$k$ 回の合成を $C^k,T^k$ と書く。
$n$ が奇数のとき $3n+1$ は偶数なので $T(n)=C^2(n)$ であり、$n$ が偶数のとき $T(n)=C(n)$ である。$T$ は $C$ の「奇数のあとの $2$ で割る操作を 1 回にまとめた」写像である。
すべての正の整数 $n$ について、$C^k(n)=1$ となる $k\ge0$ がある。
$1$ に到達すると、そのあとは $1\to4\to2\to1$ を繰り返す。$T$ で見ると $1\to2\to1$ である。
$n=7$ の $C$ の軌道は
$$
7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1
$$
である。$n=27$ は、$C$ で $111$ 回かかって $1$ に着き、途中の最大値は $9232$ である。$T$ で数えると $70$ 回である。
$n\ge2$ について、$T^k(n)< n$ となる最小の $k\ge1$ を $n$ の停止時間といい、$\sigma(n)$ と書く。そのような $k$ がないとき $\sigma(n)=\infty$ とする。
次の 4 つは同値である。
- Collatz 予想が成り立つ。
- すべての正の整数 $n$ について、$T^k(n)=1$ となる $k\ge0$ がある。
- すべての $n\ge2$ について $\sigma(n)<\infty$ である。
- すべての正の整数 $n$ について $T$ の軌道は有界であり、$T$ の周期軌道は $\{1,2\}$ だけである。
1 と 2：$T$ の軌道は、$C$ の軌道から「奇数の直後の項」を除いたものである。$T(n)=C^{k}(n)$（$k=1$ または $2$）なので、2 から 1 が従う。逆に $C$ の軌道が $1$ を通るとする。除かれる項は $3m+1$（$m$ は奇数）の形で $4$ 以上なので、$1$ は除かれない。よって $1$ は $T$ の軌道にもある。
2 から 3：$n\ge2$ なら $T^k(n)=1< n$ となる $k\ge1$ がある。
3 から 2：$n$ についての強い帰納法による。$n=1$ は $k=0$ でよい。$n\ge2$ なら $m:=T^{\sigma(n)}(n)< n$ で、$m$ は正の整数だから、帰納法の仮定により $m$ の軌道は $1$ を通る。
2 から 4：軌道は $1$ に着いたあと $\{1,2\}$ の中にあるので有界である。周期軌道の点はその周期軌道にとどまるので、$1$ を通り、周期軌道は $\{1,2\}$ である。
4 から 2：有界な軌道は同じ値を 2 度とるので、いつか周期軌道に入る。周期軌道は $\{1,2\}$ だけなので、$1$ を通る。$\square$
4 は、予想の反例が 2 種類に限られることを述べている。$\{1,2\}$ 以外の周期軌道か、無限大へ発散する軌道である。どちらも、1 つも見つかっていない。
直感
偶奇が公平なコイン投げのように現れると仮定する。$T$ は $n$ を、奇数なら約 $3/2$ 倍し、偶数なら $1/2$ 倍する。1 回あたりの $\log n$ の増分の平均は
$$
\frac12\log\frac32+\frac12\log\frac12=\frac12\log\frac34\approx-0.14384
$$
で負である。したがって「平均すると軌道は下がる」はずで、$1$ に着くまでの回数は約 $6.95212\log n$ と見積もられる（Lag21 §3.3, p. 8）。
難しいのは、この見積もりを個々の $n$ について正当化できないことである。最初の数回の偶奇だけなら本当にコイン投げと同じ分布になる（thm-clz-parity）。そこから、ほとんどすべての $n$ で 1 回は下がることが分かる（thm-clz-terras）。しかし、下がった先の数がどんな分布をしているかは分からないので、この議論を繰り返すことはできない（Tao22 §1.1, p. 2）。一方で、次の例が示すとおり、軌道が長く上がり続ける $n$ は実際にある。
$n=2^m-1$（$m\ge1$）のとき、$0\le k\le m$ について
$$
T^k(2^m-1)=3^k2^{m-k}-1
$$
である（Lag21 §3.2, p. 6）。実際、$k=0$ は明らかで、$k< m$ のとき $x=3^k2^{m-k}-1$ は奇数なので
$$
T(x)=\frac{3^{k+1}2^{m-k}-2}{2}=3^{k+1}2^{m-k-1}-1
$$
となる。$3^k2^{m-k}\ge2^m$ なので、$k\le m$ のあいだ軌道は $n$ を下回らない。よって $m\ge2$ のとき $\sigma(2^m-1)>m$ であり、停止時間に一様な上界はない。$m$ 回目の値 $3^m-1$ は $n$ の約 $(3/2)^m$ 倍である。
偶奇の並び
$n$ の軌道の偶奇を $e_j(n)\in\{0,1\}$ で表す。$T^j(n)$ が奇数なら $e_j(n)=1$、偶数なら $e_j(n)=0$ とする。すると $T(x)=(3^{e}x+e)/2$（$e$ は $x$ の偶奇）である。$a_k(n):=e_0(n)+\cdots+e_{k-1}(n)$ は、最初の $k$ 回のうち奇数だった回数である。
$k\ge0$ について、$T^k(n)=\lambda_k n+\rho_k$ と書ける。ここで $\lambda_k=3^{a_k(n)}/2^k$ であり、有理数 $\rho_k$ は $(e_0(n),\dots,e_{k-1}(n))$ だけで決まり、$0\le\rho_k\le(3/2)^k-1$ を満たす。
$\lambda_0=1$、$\rho_0=0$ である。$T^{k+1}(n)=\bigl(3^{e_k}(\lambda_kn+\rho_k)+e_k\bigr)/2$ なので $\lambda_{k+1}=3^{e_k}\lambda_k/2$、$\rho_{k+1}=(3^{e_k}\rho_k+e_k)/2$ である。これで $\lambda_k$ の式と、$\rho_k$ が偶奇の並びだけで決まることが分かる。$\rho_{k+1}\ge0$ は明らかで、$\rho_{k+1}\le(3\rho_k+1)/2$ から $\rho_{k+1}+1\le\frac32(\rho_k+1)$ となるので、$\rho_k+1\le(3/2)^k$ である。$\square$
$k\ge1$ とする。正の整数 $n,n'$ について、$n\equiv n'\pmod{2^k}$ であることと、$e_j(n)=e_j(n')$（$0\le j< k$）であることは同値である。したがって
$$
\mathbb{Z}/2^k\mathbb{Z}\to\{0,1\}^k,\qquad n\bmod2^k\mapsto(e_0(n),\dots,e_{k-1}(n))
$$
は全単射である。
$k$ についての帰納法で同値を示す。$k=1$ は $e_0$ が $n$ の偶奇そのものであることによる。$k$ で正しいとする。
$n\equiv n'\pmod{2^{k+1}}$ とする。$2^k$ を法としても合同なので、帰納法の仮定より $j< k$ の $e_j$ は一致する。lem-clz-affine より $\lambda_k,\rho_k$ は共通で、
$$
T^k(n)-T^k(n')=\frac{3^{a_k(n)}}{2^k}(n-n')
$$
である。$n-n'$ は $2^{k+1}$ で割り切れるので右辺は偶数であり、$e_k(n)=e_k(n')$ となる。
逆に $e_j(n)=e_j(n')$（$j\le k$）とする。帰納法の仮定より $n-n'$ は $2^k$ で割り切れる。上の等式の左辺は $e_k$ が一致するので偶数であり、$3^{a_k(n)}$ は奇数なので、$(n-n')/2^k$ は偶数である。よって $n\equiv n'\pmod{2^{k+1}}$ である。
同値から、写像が定義されていて単射であることが分かる。両辺の元の個数はともに $2^k$ なので全単射である。$\square$
この定理は Terras と Everett が独立に見いだしたものである（Lag21 §3.3, p. 8 と §7, p. 18）。定理は、$n$ を $2^k$ を法として一様に選ぶと、$(e_0,\dots,e_{k-1})$ が公平なコインを $k$ 回投げた結果と同じ分布になることを述べている。
$T$ は 2 進整数の環 $\mathbb{Z}_2$（p進整数）へ連続に延び、定理の極限として、偶奇の無限列を与える写像 $\mathbb{Z}_2\to\{0,1\}^{\mathbb{N}}$ は全単射になる。この写像で $T$ は列の左シフトに移る。とくに、$\mathbb{Z}_2$ の Haar 測度は $T$ で保たれ、$T$ はエルゴード的である（Lag21 §5, p. 13）。ただし正の整数は $\mathbb{Z}_2$ の中で測度 $0$ の集合なので、ここから予想については何も言えない。
ほとんどすべての整数で軌道は下がる
正の整数の集合 $A$ の下側の自然密度を $\liminf_{x\to\infty}\#(A\cap[1,x])/x$ と定める。これが $1$ のとき、$A$ の補集合の密度は $0$ で、$A$ の（自然）密度は $1$ であるという。
$\{n\ge2\mid\sigma(n)<\infty\}$ の自然密度は $1$ である。すなわち、ほとんどすべての $n$ について、$n$ より小さい値が $T$ の軌道に現れる。
$\theta:=\log2/\log3=0.6309\ldots$ とおく。$\theta>1/2$ であり、$3^a< 2^k$ と $a<\theta k$ は同値である。$k\ge1$ を固定し、
$$
B_k:=\{r\in\mathbb{Z}/2^k\mathbb{Z}\mid n\equiv r\text{ のとき }a_k(n)<\theta k\}
$$
とおく。thm-clz-parity により $a_k(n)$ は $n\bmod2^k$ で決まるので、これは定義できる。さらに同じ定理から、$\#(\mathbb{Z}/2^k\mathbb{Z}\setminus B_k)/2^k$ は、二項分布 $\mathrm{Bin}(k,1/2)$ に従う $S$ が $S\ge\theta k$ となる確率に等しい。Chebyshevの不等式 により
$$
P(S\ge\theta k)\le P\Bigl(\bigl|S-\tfrac k2\bigr|\ge(\theta-\tfrac12)k\Bigr)\le\frac{k/4}{(\theta-\frac12)^2k^2}=\frac{c}{k},\qquad c:=\frac1{4(\theta-\frac12)^2}
$$
である。
$n\bmod2^k\in B_k$ かつ $n\ge3^k$ とする。$3^{a_k(n)}<2^k$ はどちらも整数なので $\lambda_k\le1-2^{-k}$ であり、lem-clz-affine より
$$
T^k(n)=\lambda_kn+\rho_k\le n-2^{-k}n+\rho_k< n-\Bigl(\frac32\Bigr)^k+\Bigl(\frac32\Bigr)^k=n
$$
となる（$2^{-k}n\ge(3/2)^k$ と $\rho_k<(3/2)^k$ を使った）。よって $\sigma(n)\le k$ である。
長さ $2^k$ の連続する整数の各区間には、$B_k$ の剰余類の元が $\#B_k\ge(1-c/k)2^k$ 個ある。したがって、$\sigma(n)<\infty$ となる $n$ の全体の下側の自然密度は $1-c/k$ 以上である。$k$ は任意なので、下側の自然密度は $1$ である。$\square$
この定理は Terras と、独立に Everett によって示された（Tao22 §1.1, p. 2）。上の証明は、thm-clz-parity と二項分布の評価だけで済むように、$k$ 回ちょうどで下がる場合だけを数えた形である。
密度を $1$ で止めず、どれくらいの割合が何回以内に下がるかも具体的に計算できる。
$n\ge2$ について、次が成り立つ。
- $n$ が偶数なら $T(n)=n/2< n$ である。
- $n\equiv1\pmod4$ なら $T^2(n)=(3n+1)/4< n$ である。
- $n\equiv3\pmod{16}$ なら $T^4(n)=(9n+5)/16< n$ である。たとえば $n=16m+3$ で $T^4(n)=9m+2$ である。
この 3 つで $16$ を法とする剰余類のうち $13$ 個が片づき、残りは $7,11,15$ である。
一般に、$r_k$ を「$j\le k$ のどの段でも $3^{a_j}\ge2^j$ のままである剰余類（$2^k$ を法とする）の個数」とする。lem-clz-affine により、それ以外の剰余類の $n$ は、$n$ が十分大きければ $k$ 回以内に下がる。
| $k$ | $1$ | $2$ | $4$ | $5$ | $7$ | $8$ | $10$ | $12$ | $14$ | $16$ |
|---|---|---|---|---|---|---|---|---|---|---|
| $r_k$ | $1$ | $1$ | $3$ | $4$ | $13$ | $19$ | $64$ | $226$ | $734$ | $2114$ |
| $r_k/2^k$ | $0.5$ | $0.25$ | $0.1875$ | $0.125$ | $0.1016$ | $0.0742$ | $0.0625$ | $0.0552$ | $0.0448$ | $0.0323$ |
$r_k/2^k$ は $0$ に近づくが、その速さは遅い。thm-clz-terras の証明は、$r_k/2^k$ が $c/k$ 以下であることを示している。
周期軌道の条件
$\{1,2\}$ 以外の周期軌道があるとしたら、それは非常に長い。次の定理は、その理由の基本となる不等式である。
$T$ の周期軌道が $p$ 個の正の整数からなり、そのうち $a$ 個が奇数であるとする。周期軌道の最小の元を $m$ とすると
$$
\frac{2^p}{3^a}=\prod_{x\text{ は軌道の奇数の元}}\Bigl(1+\frac1{3x}\Bigr),\qquad
0< p\log2-a\log3<\frac{a}{3m}
$$
である。
軌道の元 $x$ について $T(x)/x$ を掛け合わせると、周期軌道なので積は $1$ である。$x$ が偶数なら $T(x)/x=1/2$、奇数なら $T(x)/x=\frac32\bigl(1+\frac1{3x}\bigr)$ なので
$$
1=\frac{3^a}{2^p}\prod_{x\text{ は奇数}}\Bigl(1+\frac1{3x}\Bigr)
$$
となる。これが等式である。$a\ge1$ である（偶数だけの周期軌道はない）。対数をとると、$0<\log(1+1/(3x))<1/(3x)\le1/(3m)$ より不等式を得る。$\square$
奇数をちょうど 1 個しか含まない周期軌道は $\{1,2\}$ だけである。
奇数の元を $x$ とする。thm-clz-cycle の等式は $2^p/3=1+1/(3x)$、すなわち $x(2^p-3)=1$ である。$x$ は正の整数なので $x=1$、$2^p=4$ であり、$p=2$ である。$\square$
thm-clz-cycle を $a\log2$ で割ると
$$
0<\frac pa-\log_23<\frac1{3m\log2}
$$
となる。つまり $p/a$ は $\log_23$ の非常によい有理数近似である。連分数 の理論により、そのような分数の分母は限られている。
$2^{71}$ まで予想が確かめられている（Bar25 p. 1）ので、$\{1,2\}$ 以外の周期軌道があれば $m>2^{71}$ である。このとき $0< p/a-\log_23<2.04\times10^{-22}$ である。$\log_23$ の連分数展開は $[1;1,1,2,2,3,1,5,2,23,2,2,1,1,55,1,4,3,1,1,15,1,9,2,5,\dots]$ で、$\log_23$ より大きく、差がこの値より小さい分数のうち分母が最小のものは、$114208327604/72057431991$ である（差は約 $1.10\times10^{-22}$）。よって、そのような周期軌道は奇数を少なくとも $72057431991$ 個含む。
同じ計算を $m>20\cdot2^{58}$（検証の範囲が $2^{71}$ より狭かった時点の値。Lag21 §6.1 (W1), p. 14）で行うと、分数 $10439860591/6586818670$ が得られる。この分母と分子は、Eliahou の結果「周期の長さが $10439860591$ 未満、または奇数の個数が $6586818670$ 未満の周期軌道は $\{1,2\}$ だけである」（同 (W2), pp. 14–15）に現れる値に一致する。
Hercher は別の数え方で、周期軌道の中の局所最小の個数が $92$ 以上であることを示している（Her23 Abstract, p. 1）。
知られている部分的な結果
次の結果は、この記事では証明しない。
| 方向 | 結果 | 所在 |
|---|---|---|
| 計算による確認 | $2^{71}$ までのすべての開始値で予想は正しい | Bar25 p. 1 |
| $1$ に到達する数の個数 | 十分大きい $x$ について、$x$ 以下で $1$ に到達する正の整数は $x^{0.84}$ 個以上ある（Krasikov–Lagarias） | Lag21 §6.1 (W5), p. 15 |
| 軌道の最小値の上界 | $\varepsilon>\frac{\log3}{\log4}\approx0.7924$ なら、ほとんどすべての $N$ で軌道の最小値は $N^{\varepsilon}$ より小さい（Korec。これより前に Allouche） | Tao22 §1.1, p. 2 |
| 同上 | 下の Tao の定理 | Tao22 Theorem 1.3, p. 3 |
| 問題の一般化 | $3x+1$ に似た写像の広い類には、決定不能な反復の問題が含まれる（Conway ら） | Lag21 §6.2, p. 15 と §7, pp. 18–19 |
$\mathrm{Col}_{\min}(N)$ を $N$ の $C$ の軌道の最小値とする。$f\colon\mathbb{N}_{>0}\to\mathbb{R}$ が $\lim_{N\to\infty}f(N)=+\infty$ を満たすなら、対数密度の意味でほとんどすべての $N$ について $\mathrm{Col}_{\min}(N)< f(N)$ である（Tao22 Theorem 1.3, p. 3）。
ここで対数密度とは、$A\subset\mathbb{N}_{>0}$ について
$$
\lim_{x\to\infty}\Bigl(\sum_{N\in A,\,N\le x}\frac1N\Bigr)\Bigm/\Bigl(\sum_{N\le x}\frac1N\Bigr)
$$
のことである（Tao22 Definition 1.2, p. 2）。たとえば $f(N)=\log\log\log\log N$ と取れるので、ほとんどすべての軌道が元の数に比べて極端に小さい値まで下がる。ただし、これは「ほとんどすべての $N$ で $1$ に到達する」という主張ではない。ある定数 $C_0$ で $\mathrm{Col}_{\min}(N)\le C_0$ がほとんどすべての $N$ で成り立つ、という形に強めることさえ、予想とほぼ同じくらい難しいと Tao は述べている（同 Remark 1.4, p. 3）。発散する軌道や未知の周期軌道があっても、それは密度 $0$ の集合の中に隠れている可能性があるので、密度の議論だけでは予想に届かない。
証明は Collatz の反復を奇数の間だけで見る写像に書き換え、それを $3$ 進の巡回群 $\mathbb{Z}/3^n\mathbb{Z}$ の上のランダムウォークの問題に帰着する（Tao22 Abstract, p. 1）。thm-clz-terras の議論を繰り返せない原因だった「下がった先の分布」の問題を、繰り返しに耐える確率測度の族を見つけることで克服している（同 §1.1, p. 2）。
反例：写像を変えると成り立たない
予想は「$3$ と $1$ と正の整数」という設定に強く依存している。次の表は設定の 1 か所だけを変えた例である。どの場合も、値 $1$ に到達しない軌道がある。確かめは 1 周分の直接の計算である。
| 変える設定 | 周期軌道の例（$C$ に相当する写像の軌道） | 破れること |
|---|---|---|
| 定義域を負の整数へ広げる | $-5\to-14\to-7\to-20\to-10\to-5$ | 周期軌道が 1 つだけであること |
| $3x+1$ を $5x+1$ に変える | $13\to66\to33\to166\to83\to416\to208\to104\to52\to26\to13$ | すべての正の整数が $1$ に到達すること |
| $3x+1$ を $3x+5$ に変える | $19\to62\to31\to98\to49\to152\to76\to38\to19$ | $1$ を通る周期軌道だけであること |
$5x+1$ の場合には、確率モデルは 1 回あたりの対数の増分の平均を正と予測する。ほとんどすべての軌道が発散すると予想されるが、発散する軌道が 1 つでもあることの証明は知られていない（Lag21 §3.3, p. 9）。Collatz 予想の直感の根拠だった「平均すると下がる」が、ここで係数に依存していることが分かる。
また、ex-clz-mersenne は、「ある定数 $K$ があって、すべての $n$ で $\sigma(n)\le K$」という強い主張への反例である。thm-clz-terras の「ほとんどすべて」は、「すべて」には置き換えられない形で証明されている。
補足
名前。 問題は長く口伝えで広まり、1970 年代の初めまで数学の文献としては刊行されなかった（Lag21 §2, pp. 3–4）。Collatz に由来するとされるが、起源には別の主張もある（Lag21 §2, p. 3）。1950 年の国際数学者会議には Coxeter、角谷、Ulam らが招待講演者として参加しており、のちに彼らの名が問題と結びついた（同 p. 3）。
なぜ難しいか。 $T$ は、整数の上で大きくする部分と小さくする部分を持つ反復の典型であり、軌道の疑似乱数的な性質を解析できないことが困難の一部だと考えられている（Lag21 §1, p. 2）。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
