# コラッツ予想：3行で書けるのに誰も解けない問題

> 偶数なら半分、奇数なら3倍して1を足す。この単純な規則がなぜ90年間解けないのかを、実際に証明できる部分（巡回の非存在、密度3/4の減少）と確率的ヒューリスティック、3n−1版の反例から具体的に解説する。
> https://rikai.mugen-giken.com/mathematics/math-columns/collatz-conjecture

## 0. この記事の要点

- ルールはたった 2 行です。自然数 $n$ が偶数なら $n/2$、奇数なら $3n+1$ に置き換える。これを繰り返すと必ず $1$ にたどり着く——これがコラッツ予想で、1930 年代に提出されて以来未解決です。
- 小さい数で試すとすぐ $1$ に落ちます。ところが $27$ から始めると $111$ 手かかり、途中で $9232$ まで跳ね上がります。「単純＝易しい」ではないことを、この 1 例が教えてくれます。
- 何も分かっていないわけではありません。「奇数が 1 個または 2 個だけの巡回は自明なもの以外に存在しない」「少なくとも 4 分の 3 の自然数は 3 手以内に元より小さくなる」といった主張は、この記事の中で完全に証明できます。
- 「たぶん正しい」と信じられている理由は、1 手あたり平均して $\sqrt{3/4} \approx 0.866$ 倍に縮むという確率的な見積もりです。ただしこれは証明ではありません。
- $3n+1$ を $3n-1$ に変えるだけで反例（$5 \to 14 \to 7 \to 20 \to 10 \to 5$）が現れます。つまり正しい証明は「$+1$ か $-1$ か」を区別できるほど繊細でなければならず、そこが最大の壁です。

## 1. 動機：ルールを 3 行で書ける未解決問題

数学の未解決問題というと、ふつうは問題文を理解するだけでひと苦労します。リーマン予想を人に説明しようとすれば、まず複素数とゼータ関数の話から始めなければなりません。

コラッツ予想はそうではありません。ルールはこれだけです。

1. 自然数を 1 つ選ぶ。
2. それが偶数なら 2 で割る。奇数なら 3 倍して 1 を足す。
3. 2 に戻る。

そして予想はこうです。**どんな自然数から始めても、いつかは $1$ に到達する。**

小学生でも遊べます。実際に $6$ から始めてみましょう。

$$
6 \to 3 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1
$$

$8$ 手で着地しました。$1$ に着いたあとは $1 \to 4 \to 2 \to 1$ とぐるぐる回るので、そこで打ち切ります。

この問題は、1937 年頃にドイツの数学者ローター・コラッツが提出したとされます。以来、角谷静夫にちなむ「角谷の問題」、ウラム、ハッセ、スウェイツなど多くの名前が付き、「シラキュース問題」「$3n+1$ 問題」とも呼ばれてきました。名前が多いというのは、それだけ多くの人が独立に取り憑かれたということです。

エルデシュ・パールはこの問題に 500 ドルの懸賞をかけたうえで、現代の数学はまだこの種の問題を扱えるほど成熟していない、という趣旨のことを述べたと伝えられています。2021 年には日本の企業が 1 億 2000 万円の懸賞金を出したことも話題になりました。それでもまだ解けていません。

<Aside type="caution">
この問題には「ちょっと考えたら解けそうな気がする」という危険な魅力があります。実際、数論の研究者はコラッツ予想の「証明」を送りつけられることに慣れています。この記事を読み終えたときには、なぜ素朴な方針がことごとく失敗するのかが分かるようにしたいと思います。
</Aside>

## 2. 準備：コラッツ写像・軌道・停止時間

遊びを数学にするために、言葉を決めます。以下、$\mathbb{N} = \{1, 2, 3, \ldots\}$ とし、$0$ は含めません。

<Definition id="def-collatz" title="コラッツ写像">
写像 $C : \mathbb{N} \to \mathbb{N}$ を
$$
C(n) = \begin{cases} n/2 & (n \text{ が偶数}) \\ 3n+1 & (n \text{ が奇数}) \end{cases}
$$
で定める。これを**コラッツ写像**と呼ぶ。
</Definition>

$n$ が奇数のとき $3n+1$ は必ず偶数なので、奇数の次には必ず偶数が来ます。そこで「奇数のときは $3n+1$ してすぐ 2 で割る」とまとめた写像も便利です。

<Definition id="def-shortcut" title="短縮コラッツ写像">
写像 $T : \mathbb{N} \to \mathbb{N}$ を
$$
T(n) = \begin{cases} n/2 & (n \text{ が偶数}) \\ (3n+1)/2 & (n \text{ が奇数}) \end{cases}
$$
で定める。これを**短縮コラッツ写像**と呼ぶ。
</Definition>

$T$ は $C$ の 1 手または 2 手をまとめたものなので、$C$ で $1$ に到達することと $T$ で $1$ に到達することは同値です。証明では計算が短くなる方を使います。

<Definition id="def-orbit" title="軌道・停止時間・巡回">
$n \in \mathbb{N}$ に対し、列 $n,\, C(n),\, C^2(n),\, \ldots$ を $n$ の**軌道**と呼ぶ。

$$
\sigma(n) = \min\{\, k \ge 1 : C^k(n) < n \,\}
$$
を $n$ の**停止時間**と呼ぶ（そのような $k$ が存在しないときは $\sigma(n) = \infty$ と定める）。

また、$C^k(m) = m$ となる $k \ge 1$ が存在するとき、$m$ を含む有限集合 $\{m, C(m), \ldots, C^{k-1}(m)\}$ を**巡回**と呼ぶ。
</Definition>

停止時間は「元の数より小さくなるまでに何手かかるか」です。$1$ に着くまでの手数（総停止時間）より扱いやすく、後で見るようにこちらだけで予想を言い換えられます。

<Figure caption="コラッツ写像の 1 手">
<Mermaid code={`flowchart LR
  A["自然数 n"] --> B&#123;"n は偶数か"&#125;
  B -- "はい" --> C["n / 2 に置き換える"]
  B -- "いいえ" --> D["3n + 1 に置き換える"]
  C --> E&#123;"n = 1 か"&#125;
  D --> E
  E -- "いいえ" --> A
  E -- "はい" --> F["終了"]`} />
</Figure>

## 3. まず手を動かす

理屈より先に、数を眺めます。

<Example id="ex-small-numbers" title="1 から 12 までの成績表">
各 $n$ について、$1$ に到達するまでの手数（総停止時間）と、軌道の最大値を並べます。

| $n$ | 手数 | 軌道の最大値 |
|---|---|---|
| 1 | 0 | 1 |
| 2 | 1 | 2 |
| 3 | 7 | 16 |
| 4 | 2 | 4 |
| 5 | 5 | 16 |
| 6 | 8 | 16 |
| 7 | 16 | 52 |
| 8 | 3 | 8 |
| 9 | 19 | 52 |
| 10 | 6 | 16 |
| 11 | 14 | 52 |
| 12 | 9 | 16 |

たとえば $7$ の軌道は
$$
7 \to 22 \to 11 \to 34 \to 17 \to 52 \to 26 \to 13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1
$$
で、確かに 16 手、最大値 $52$ です。隣り合う $6$ と $7$ で手数が $8$ と $16$、$8$ と $9$ で $3$ と $19$ と、まったく揃いません。この不規則さがこの問題の本質です。
</Example>

<Example id="ex-27" title="27 という暴れ者">
$27$ から始めると、軌道はこう動き出します。
$$
27 \to 82 \to 41 \to 124 \to 62 \to 31 \to 94 \to 47 \to 142 \to 71 \to 214 \to 107 \to \cdots
$$
下がったかと思うとまた上がる、を延々と繰り返し、途中で最大値 $9232$ に達し、$111$ 手かけてようやく $1$ に着きます。出発点は $27$、つまり $2$ 桁です。それが $4$ 桁まで登るのです。

$27$ の隣の $26$ は $10$ 手、$28$ は $18$ 手で終わります。$27$ だけが突出しているわけで、「小さい数だから短いはず」という直感はここで完全に壊れます。
</Example>

手で追うのは大変なので、プログラムに任せます。次のコードは標準ライブラリだけで動きます。

```python
def total_stopping_time(n):
    """n が 1 に到達するまでの手数と軌道の最大値を返す。"""
    steps, peak = 0, n
    while n != 1:
        n = n // 2 if n % 2 == 0 else 3 * n + 1
        peak = max(peak, n)
        steps += 1
    return steps, peak

print(total_stopping_time(27))   # (111, 9232)
print(max(range(1, 10**6), key=lambda n: total_stopping_time(n)[0]))
# 837799 （100 万未満で最も手数が多い数。524 手）
```

最後の行を実行すると $837799$ が返ります。手数は $524$ です。$100$ 万未満の数で最悪でも $524$ 手、というのは「意外と小さい」と感じるでしょうか。それとも「$1$ に着く保証がないのに $524$ 手も彷徨うのか」と感じるでしょうか。どちらの感想も正しいのが、この問題の面白いところです。

## 4. 定義からすぐ証明できること

「何も分かっていない」わけではありません。ここでは紙と鉛筆だけで証明できる事実を 3 つ挙げます。

<Theorem id="thm-powers-of-two" title="2 の冪は素直">
$k \ge 0$ を整数とすると、$C^k(2^k) = 1$ である。すなわち $2^k$ はちょうど $k$ 手で $1$ に到達する。
</Theorem>

<Proof of="thm-powers-of-two">
$k$ についての帰納法で示します。$k = 0$ のとき $2^0 = 1$ で、$C^0(1) = 1$ ですから成立します。

$k$ で成立するとします。$2^{k+1}$ は偶数なので、<Ref to="def-collatz" /> より $C(2^{k+1}) = 2^{k+1}/2 = 2^k$ です。よって
$$
C^{k+1}(2^{k+1}) = C^{k}\bigl(C(2^{k+1})\bigr) = C^k(2^k) = 1
$$
となり、最後の等号で帰納法の仮定を使いました。以上で $k+1$ でも成立します。
</Proof>

つまり $2, 4, 8, 16, 32, \ldots$ は一直線に落ちます。予想が難しいのは、こういう素直な数のせいではありません。

<Proposition id="prop-mod4" title="4 で割って 1 余る数は 3 手で小さくなる">
$n$ を偶数とすると $\sigma(n) = 1$ である。また $n \ge 5$ が $n \equiv 1 \pmod 4$ を満たすならば $\sigma(n) = 3$ であり、しかも
$$
C^3(n) = \frac{3n+1}{4}
$$
が成り立つ。したがって、$\sigma(n) \le 3$ を満たす自然数の（自然密度の意味での）割合は少なくとも $3/4$ である。
</Proposition>

<Proof of="prop-mod4">
$n$ が偶数なら <Ref to="def-collatz" /> より $C(n) = n/2 < n$ なので $\sigma(n) = 1$ です。

次に $n \equiv 1 \pmod 4$、$n \ge 5$ とし、$n = 4k+1$（$k \ge 1$）と書きます。$n$ は奇数なので
$$
C(n) = 3(4k+1)+1 = 12k+4 .
$$
これは偶数なので $C^2(n) = 6k+2$、これも偶数なので $C^3(n) = 3k+1$ です。ここで
$$
\frac{3n+1}{4} = \frac{12k+3+1}{4} = 3k+1
$$
なので、主張の等式が確かめられました。

$\sigma(n) = 3$ であることを見ます。まず $C^3(n) = 3k+1 < 4k+1 = n$ は $k \ge 1$ から従います。一方、途中の 2 手では小さくなりません。実際 $C(n) = 12k+4 > 4k+1 = n$（$8k+3 > 0$ より）、$C^2(n) = 6k+2 > 4k+1 = n$（$2k+1 > 0$ より）です。よって $n$ より小さくなる最初の時刻はちょうど $3$ です。

最後に密度を数えます。$1$ 以上 $N$ 以下の自然数のうち、偶数はおよそ $N/2$ 個、$4$ で割って $1$ 余るものはおよそ $N/4$ 個あり、両者は重なりません。したがって $\sigma(n) \le 3$ を満たすものは少なくともおよそ $N/2 + N/4 = 3N/4$ 個あり、$N \to \infty$ として割合 $3/4$ 以上を得ます。
</Proof>

この計算は「もっと細かい剰余で調べれば、もっと多くの $n$ を捕まえられるのでは」という発想につながります。実際そのとおりです。なお、以下でも使う $a \equiv b \pmod m$ という合同の記法については <Ref to="mathematics/math-columns/why-math-is-hard#def-congruence" text="合同の定義" /> を参照してください。

<Example id="ex-mod16" title="16 で割って 3 余る数も落ちる">
$n \equiv 3 \pmod{16}$、すなわち $n = 16k+3$（$k \ge 0$）とします。$C$ を 6 回適用します。
$$
16k+3 \to 48k+10 \to 24k+5 \to 72k+16 \to 36k+8 \to 18k+4 \to 9k+2
$$
最後の $9k+2$ は $16k+3$ より小さい（差は $7k+1 > 0$）ので、$\sigma(n) \le 6$ です。$n \equiv 3 \pmod{16}$ の数は全体の $1/16$ を占め、これは <Ref to="prop-mod4" /> で捕まえた偶数とも $1 \bmod 4$ とも重なりません（$3 \bmod 16$ の数は $3 \bmod 4$ の奇数だからです）。合わせて割合は $1/2 + 1/4 + 1/16 = 13/16$ 以上になります。
</Example>

この手続きを $\bmod 2^k$ でどこまでも続けると、次の定理が得られます。

<Remark id="rem-terras">
テラス（R. Terras, 1976）は、$\sigma(n) < \infty$ を満たす $n$ の自然密度が $1$ であることを証明しました。つまり「ほとんどすべての自然数は、いつか自分より小さくなる」までは分かっています。これは <Ref to="prop-mod4" /> と <Ref to="ex-mod16" /> の手続きを $\bmod 2^k$ で押し切り、$k \to \infty$ としたものです。ただし密度 $1$ は「例外が有限個」を意味しません。例外の集合が無限にあっても密度は $0$ になり得ます。
</Remark>

停止時間だけを見ればよい、というのは次の言い換えから正当化されます。

<Theorem id="thm-equivalent-stopping" title="停止時間による言い換え">
次の 2 つは同値である。

(a) すべての $n \in \mathbb{N}$ の軌道は $1$ を含む（コラッツ予想）。

(b) すべての $n \ge 2$ に対して $\sigma(n) < \infty$ である。
</Theorem>

<Proof of="thm-equivalent-stopping">
**(a) $\Rightarrow$ (b)。** $n \ge 2$ とします。(a) より、ある $k \ge 0$ で $C^k(n) = 1$ です。$n \ge 2 > 1$ なので $k \ge 1$ であり、$C^k(n) = 1 < n$ です。よって $n$ より小さくなる時刻が少なくとも 1 つ存在し、その最小値 $\sigma(n)$ は有限です。

**(b) $\Rightarrow$ (a)。** $n$ についての強い帰納法で「$n$ の軌道は $1$ を含む」を示します。

$n = 1$ のときは軌道の最初の項が $1$ なので成立します。

$n \ge 2$ とし、$n$ より小さいすべての自然数について主張が成り立つと仮定します。(b) より $k = \sigma(n)$ は有限で、$m = C^k(n)$ とおくと $m < n$、かつ $m \ge 1$ です。帰納法の仮定より $m$ の軌道は $1$ を含み、ある $j \ge 0$ で $C^j(m) = 1$ となります。すると
$$
C^{k+j}(n) = C^j\bigl(C^k(n)\bigr) = C^j(m) = 1
$$
なので、$n$ の軌道も $1$ を含みます。
</Proof>

<Aside type="tip">
<Ref to="thm-equivalent-stopping" /> は「無限の彼方まで追跡する」問題を「有限手で一度でも下がるか」という問題に置き換えます。無限に関する主張を有限に関する主張へ落とす、この種の言い換えは数学のあらゆる場面で使われます。
</Aside>

## 5. ぐるぐる回る危険：巡回は存在するか

予想が破れるとしたら、破れ方は 2 通りしかありません。

1. どこかの $n$ の軌道が $1$ を含まない巡回に入る。
2. どこかの $n$ の軌道が無限に大きくなり続ける（<Ref to="mathematics/math-columns/division-by-zero#def-divergence" text="正の無限大に発散する" />）。

このうち 1 については、かなりのことが証明できます。

<Lemma id="lem-cycle-has-odd" title="巡回は奇数を含む">
$C$ の任意の巡回は、少なくとも 1 つの奇数を含む。
</Lemma>

<Proof of="lem-cycle-has-odd">
巡回 $\{m, C(m), \ldots, C^{k-1}(m)\}$ がすべて偶数からなると仮定します。すると <Ref to="def-collatz" /> より各項は前の項の半分なので、$C^k(m) = m/2^k$ です。巡回の定義から $C^k(m) = m$ なので $m = m/2^k$、すなわち $m(2^k - 1) = 0$ となります。$k \ge 1$ より $2^k - 1 \ge 1$ なので $m = 0$ ですが、これは $m \in \mathbb{N}$ に反します。
</Proof>

巡回に含まれる奇数を順に $n_1, n_2, \ldots, n_r$（互いに相異なる）とします。$n_i$ が奇数なら $3n_i + 1$ は偶数で、そこから偶数が続く限り 2 で割られ、次の奇数 $n_{i+1}$（添字は $r$ の次を $1$ と読む）に着きます。割った回数を $a_i \ge 1$ とすると
$$
3 n_i + 1 = 2^{a_i} n_{i+1} \qquad (i = 1, \ldots, r)
$$
が成り立ちます。この関係式が巡回を調べる出発点です。

<Theorem id="thm-cycle-two-odds" title="奇数が 2 個以下の巡回">
$C$ の巡回で、含まれる奇数の個数が $1$ 個または $2$ 個であるものは、$\{1, 4, 2\}$ に限る。
</Theorem>

<Proof of="thm-cycle-two-odds">
<Ref to="lem-cycle-has-odd" /> より奇数は少なくとも 1 個あります。上で導いた関係式を使います。

**奇数が 1 個の場合。** $r = 1$ なら $n_2 = n_1 = n$ と読み替えて $3n + 1 = 2^a n$、すなわち
$$
n (2^a - 3) = 1 .
$$
$n$ と $2^a - 3$ はともに整数で積が $1$、かつ $n \ge 1$ なので $n = 1$ かつ $2^a - 3 = 1$、つまり $2^a = 4$、$a = 2$ です。このとき巡回は $1 \to 4 \to 2 \to 1$ で、集合として $\{1, 4, 2\}$ です。

**奇数が 2 個の場合。** 相異なる奇数 $n_1 \ne n_2$ について
$$
3n_1 + 1 = 2^{a_1} n_2, \qquad 3n_2 + 1 = 2^{a_2} n_1
$$
が成り立つとします。辺々掛けて $A = a_1 + a_2 \ge 2$ とおくと
$$
(3n_1+1)(3n_2+1) = 2^{A} n_1 n_2 ,
$$
左辺を展開して
$$
9 n_1 n_2 + 3(n_1 + n_2) + 1 = 2^A n_1 n_2 ,
$$
すなわち
$$
(2^A - 9)\, n_1 n_2 = 3(n_1 + n_2) + 1 .
$$
右辺は正なので左辺も正で、$2^A > 9$ です。$2$ の冪で $9$ を超える最小のものは $16$ なので $2^A \ge 16$、よって $2^A - 9 \ge 7$ です。$n_1 n_2 > 0$ なので
$$
7 n_1 n_2 \le (2^A - 9)\, n_1 n_2 = 3(n_1 + n_2) + 1 .
$$
一般性を失わず $n_1 < n_2$ とします（相異なるので等号は起きません）。

$n_1 = 1$ のとき、この不等式は $7 n_2 \le 3 + 3 n_2 + 1$、すなわち $4 n_2 \le 4$ となり $n_2 \le 1$ です。これは $n_2 > n_1 = 1$ に矛盾します。

$n_1 \ge 3$ のとき（$n_1$ は奇数なので $1$ の次は $3$ です）、左辺は $7 n_1 n_2 \ge 21 n_2 = 3 n_2 + 18 n_2$ と下から評価できます。一方 $n_2 > n_1 \ge 3$ より $18 n_2 > 18 n_1 \ge 3 n_1 + 1$（$15 n_1 \ge 45 > 1$ だから）です。したがって
$$
7 n_1 n_2 \ge 3 n_2 + 18 n_2 > 3 n_2 + 3 n_1 + 1 = 3(n_1+n_2) + 1
$$
となり、先ほどの不等式に矛盾します。

以上より奇数が 2 個の巡回は存在せず、巡回は $\{1,4,2\}$ に限られます。
</Proof>

この議論は奇数の個数 $r$ を増やすと急激に難しくなりますが、同じ関係式を精密化する方向で研究が進んでいます。現在では、$1$ を含まない巡回が存在するとすれば、その長さは $10$ 億手を優に超えることが示されています。

<Figure caption="1 に流れ込む数たち（矢印は 1 手の適用）">
<Mermaid code={`flowchart LR
  n12["12"] --> n6["6"] --> n3["3"] --> n10["10"] --> n5["5"] --> n16["16"] --> n8["8"] --> n4["4"] --> n2["2"] --> n1["1"]
  n80["80"] --> n40["40"] --> n20["20"] --> n10
  n13["13"] --> n40
  n21["21"] --> n64["64"] --> n32["32"] --> n16
  n128["128"] --> n64`} />
</Figure>

この図の枝をどこまでも伸ばしていったとき、すべての自然数がこの 1 本の木の中に現れるか——それがコラッツ予想です。図を見ると $16$ には $32$ と $5$ の 2 本、$40$ には $80$ と $13$ の 2 本が流れ込んでいます。偶数 $m$ には必ず $2m$ が流れ込み、さらに $m \equiv 4 \pmod 6$ のときは奇数 $(m-1)/3$ も流れ込みます。木は上に向かって指数的に広がるので（指数的な増大がどれほど速いかは <Ref to="mathematics/math-columns/why-math-is-hard#ex-fold" text="紙を 42 回折る話" /> が分かりやすい例です）、「全部を尽くしているか」を確かめるのは目で見るほど簡単ではありません。

## 6. なぜ「たぶん正しい」と思われているのか

証明はないのに、多くの数学者はコラッツ予想が正しいと考えています。根拠は次の見積もりです。

奇数 $n$ に短縮写像 <Ref to="def-shortcut" /> を当てると $(3n+1)/2 \approx 1.5 n$、偶数に当てると $0.5 n$ です。ここで「軌道に現れる数の偶奇はコイン投げのようにランダムだ」と仮定してみます。すると 1 手あたりの倍率の**幾何平均**は
$$
\sqrt{1.5 \times 0.5} = \sqrt{0.75} \approx 0.866
$$
です。$1$ より小さい。つまり典型的な軌道は、増えたり減ったりしながら平均としては 1 手ごとに約 13% ずつ縮んでいくはずだ、というわけです。縮み続けるなら、いつかは小さな数に落ちる。落ちればあとは <Ref to="thm-equivalent-stopping" /> の帰納法が効きます。

この見積もりは手数の予測まで与えます。$C$ で考えると、奇数 1 個につき平均 2 回の halving が続く（$3n+1$ が $2^j$ でちょうど割り切れる確率が $2^{-j}$ なので期待値が $2$）ので、奇数 $k$ 個・偶数 $2k$ 個で全体の倍率は $3^k / 2^{2k} = (3/4)^k$ です。これが $1/n$ になるのは $k = \ln n / \ln(4/3)$ のときで、総手数は $3k \approx 10.4 \ln n$ と予測されます。$n$ が $100$ 万程度なら $10.4 \times 13.8 \approx 144$ 手。実測でもその近辺に集中します。悪くない予測です。

<Aside type="caution">
ただし、これは**証明ではありません**（<Ref to="mathematics/math-columns/why-math-is-hard#def-proof" text="証明とは何か" /> を思い出してください）。「軌道の偶奇がランダム」という仮定に根拠がないからです。軌道は決定論的に定まっていて、コインを振っているわけではありません。$27$ が $111$ 手もかかり $9232$ まで登ったことを思い出してください（<Ref to="ex-27" />）。ランダムなら滅多に起きないことが、実際には起きます。確率的な議論は「例外がどれくらい珍しいか」を言えても、「例外が 1 個もない」は決して言えません。
</Aside>

証明できている最良の結果は、この確率的直観を厳密化する方向にあります。テレンス・タオは 2019 年に、任意の発散関数 $f$（$f(n) \to \infty$）について、ほとんどすべての $n$ の軌道が $f(n)$ より小さい値を取ることを示しました。「ほとんどすべての $n$ はいったんは非常に小さくなる」ところまでは来ているわけです。それでも「すべての $n$ が $1$ に着く」との間には、依然として深い溝があります。

## 7. なぜ難しいのか：3n−1 という残酷な反例

素朴な証明方針が失敗する理由を、いちばん鮮明に示す例を挙げます。ルールの $+1$ を $-1$ に変えてみます。

<Proposition id="prop-3n-minus-1" title="3n−1 版には自明でない巡回がある">
写像 $D : \mathbb{N} \to \mathbb{N}$ を、$n$ が偶数なら $D(n) = n/2$、奇数なら $D(n) = 3n - 1$ で定める。このとき $D$ は $\{1, 2\}$ 以外に巡回
$$
5 \to 14 \to 7 \to 20 \to 10 \to 5
$$
をもつ。
</Proposition>

<Proof of="prop-3n-minus-1">
順に計算します。$5$ は奇数なので $D(5) = 3 \cdot 5 - 1 = 14$。$14$ は偶数なので $D(14) = 7$。$7$ は奇数なので $D(7) = 3 \cdot 7 - 1 = 20$。$20$ は偶数なので $D(20) = 10$、$10$ は偶数なので $D(10) = 5$。よって $D^5(5) = 5$ であり、$\{5, 14, 7, 20, 10\}$ は巡回です。$1$ を含まないので $\{1,2\}$ とは異なります。

なお $D(1) = 2$、$D(2) = 1$ なので $\{1,2\}$ も巡回です。
</Proof>

これが効いてきます。第 6 節の確率的な見積もりは、$+1$ を $-1$ に変えてもまったく同じです（$3n-1 \approx 3n$ ですから）。つまり「平均して縮むから $1$ に落ちる」という議論は、**反例のある問題に対しても同じ結論を出してしまう**のです。したがってこの方針は、そのままでは決して証明になりません。

<Example id="ex-negative-cycles" title="負の数まで含めるともっとひどい">
$D$ の巡回は上のものだけではありません。
$$
17 \to 50 \to 25 \to 74 \to 37 \to 110 \to 55 \to 164 \to 82 \to 41 \to 122 \to 61 \to 182 \to 91 \to 272 \to 136 \to 68 \to 34 \to 17
$$
も巡回です（各手を <Ref to="prop-3n-minus-1" /> と同じ要領で確かめてください）。

さらに、$n \mapsto -n$ と置き換えると $D$ は元のコラッツ写像 $C$ そのものになります。したがって $C$ を負の整数まで拡張すると、$-1 \to -2 \to -1$、$-5 \to -14 \to -7 \to -20 \to -10 \to -5$、そして $-17$ から始まる長さ $18$ の巡回、と 3 つの巡回が現れます。$C$ の式は正負で何も変わらないのに、正の側だけ巡回が $1$ つしかない（と予想される）——この非対称性を説明できる理屈が、今のところ誰にも見つかっていません。
</Example>

もう 1 つ、深いところからの警告があります。ジョン・コンウェイは 1972 年、コラッツ写像を「$n$ を $m$ で割った余りごとに別々の一次式を当てる」形に一般化した写像の族について、与えられた出発点が $1$ に到達するかどうかを判定する一般的アルゴリズムが存在しない（アルゴリズム的に決定不能である）ことを示しました。コラッツ予想そのものが決定不能だと言っているわけではありませんが、「この種の問題に万能の解法はない」ことが証明されている、というのは重い事実です。

<Remark id="rem-verification" title="計算による検証の現状">
コンピュータによる検証は、$2^{68} \approx 2.95 \times 10^{20}$ までのすべての自然数が $1$ に到達することを確かめています（Barina, 2021）。これは膨大ですが、無限に比べれば何でもありません。実際、最小の反例が $10^{100}$ のあたりに潜んでいたとしても、現在の検証はそれを一切排除できません。有限個の確認をいくら積み上げても証明にならないことは、<Ref to="mathematics/math-columns/why-math-is-hard#ex-prime-formula" text="40 回当たって 41 回目に外れる公式" /> が端的に示すとおりです。

一方、理論的な側からは、$x$ 以下の自然数のうち $1$ に到達するものの個数が少なくとも $x^{0.84}$ 個であること（Krasikov–Lagarias, 2003）などが示されています。$x^{0.84}$ は $x$ に比べればずっと少ない——「ほとんど全部」を数え上げる作業が、いかに難しいかが分かります。
</Remark>

## 8. 演習

<Exercise id="exr-orbit-of-seven" difficulty="易">
$C$ を <Ref to="def-collatz" /> の写像とする。$n = 9$ の軌道を書き下し、$1$ に到達するまでの手数と軌道の最大値を求めよ。
<Solution>
順に計算します。
$$
9 \to 28 \to 14 \to 7 \to 22 \to 11 \to 34 \to 17 \to 52 \to 26 \to 13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1
$$
$9$ を第 $0$ 項として数えると、$1$ は第 $19$ 項です。よって手数は $19$ です。最大値は $52$ です。

<Ref to="ex-small-numbers" /> の表で $7$ の手数が $16$ でしたが、上の軌道は 3 手目で $7$ に落ちています。$3 + 16 = 19$ で一致します。このように「途中で既知の数に合流したら、そこから先は計算し直さなくてよい」というのが、コラッツ数列を高速に計算するときの基本テクニックです。
</Solution>
</Exercise>

<Exercise id="exr-four-n-plus-one" difficulty="標準">
$n$ を奇数とする。$4n+1$ もまた奇数であることを確かめたうえで、
$$
C^3(4n+1) = C(n)
$$
を示せ。これは何を意味するか、$n = 5$ の場合で確かめよ。
<Solution>
$n$ が奇数なら $4n$ は偶数なので $4n+1$ は奇数です。よって
$$
C(4n+1) = 3(4n+1) + 1 = 12n + 4 .
$$
これは偶数なので $C^2(4n+1) = 6n + 2$、これも偶数なので
$$
C^3(4n+1) = 3n + 1 .
$$
一方 $n$ は奇数なので $C(n) = 3n+1$ です。両者は一致します。

つまり $4n+1$ の軌道は 3 手で $n$ の軌道に合流します。

$n = 5$ のとき $4n+1 = 21$ です。$21 \to 64 \to 32 \to 16$ で、$C(5) = 16$ に確かに合流しています。この事実は、<Ref to="thm-cycle-two-odds" /> の後の図で $21$ が $64$ を通って $16$ に流れ込んでいたことに対応します。奇数 $n$ に対して $n, 4n+1, 4(4n+1)+1 = 16n+5, \ldots$ が全部同じところに合流するので、コラッツの木には無限に続く「そっくりな枝」がたくさんあります。
</Solution>
</Exercise>

<Exercise id="exr-mod-sixteen" difficulty="標準">
$n \equiv 11 \pmod{16}$ を満たす $n$ は、<Ref to="ex-mod16" /> と同じ 6 手では $n$ より小さくならないことを示せ。
<Solution>
$n = 16k + 11$（$k \ge 0$）とおいて計算します。$n$ は奇数なので
$$
C(n) = 48k + 34 .
$$
偶数なので $C^2(n) = 24k + 17$、これは奇数なので $C^3(n) = 72k + 52$、偶数なので $C^4(n) = 36k + 26$、偶数なので $C^5(n) = 18k + 13$、これは奇数なので
$$
C^6(n) = 54k + 40 .
$$
$54k + 40 > 16k + 11$（差は $38k + 29 > 0$）なので、6 手では小さくなっていません。途中の値もすべて $16k+11$ より大きいことは、たとえば $C^5(n) = 18k+13 > 16k+11$（差 $2k+2 > 0$）のように順に確かめられます。

つまり <Ref to="ex-mod16" /> の手続きは剰余類ごとに「当たり外れ」があり、外れたものは $\bmod 32$、$\bmod 64$ とさらに細かく分けて調べ直すことになります。<Ref to="rem-terras" /> のテラスの定理は、この細分をどこまでも続けると取りこぼしの割合が $0$ に近づく、という主張です。
</Solution>
</Exercise>

<Exercise id="exr-two-power-minus-one" difficulty="難">
$T$ を <Ref to="def-shortcut" /> の短縮コラッツ写像とする。$k \ge 0$ と $m \ge 1$ に対して
$$
T^k(2^k m - 1) = 3^k m - 1
$$
が成り立つことを $k$ についての帰納法で示せ。これを使って、$n = 2^k - 1$ の形の数が最初のうち大きく増えることを説明せよ。
<Solution>
**$k = 0$ のとき。** 左辺は $T^0(m - 1) = m - 1$、右辺は $m - 1$ で一致します。

**$k$ で成立すると仮定して $k+1$ を示す。** $N = 2^{k+1} m - 1$ とおきます。$2^{k+1} m$ は（$k + 1 \ge 1$ なので）偶数なので $N$ は奇数です。よって <Ref to="def-shortcut" /> より
$$
T(N) = \frac{3(2^{k+1} m - 1) + 1}{2} = \frac{3 \cdot 2^{k+1} m - 2}{2} = 3 \cdot 2^{k} m - 1 = 2^k (3m) - 1 .
$$
これは $2^k m' - 1$ の形（$m' = 3m \ge 1$）なので、帰納法の仮定が使えて
$$
T^{k+1}(N) = T^k\bigl(T(N)\bigr) = T^k(2^k m' - 1) = 3^k m' - 1 = 3^k \cdot 3m - 1 = 3^{k+1} m - 1 .
$$
以上で帰納法が完成します。

**意味。** $m = 1$ とすると、$n = 2^k - 1$ は $k$ 手の短縮ステップで $3^k - 1$ になります。倍率はおよそ $(3/2)^k$ で、$k$ が大きいほど激しく増えます。第 6 節の確率的な見積もりでは「1 手あたり平均 $0.866$ 倍」でしたが、この形の数は最初の $k$ 手すべてが奇数ステップで、平均から大きく外れるのです。

たとえば $k = 5$ なら $n = 31$ で、
$$
31 \to 47 \to 71 \to 107 \to 161 \to 242
$$
と 5 手で $242$ まで登ります（$3^5 - 1 = 242$ です）。<Ref to="ex-27" /> の $27$ が暴れたのも同じ理由で、$27$ の軌道は途中で $31$ を通ります。「たまたま奇数が連続する数」はいくらでも作れるので、確率的な議論だけで予想を証明できない理由がここにも見えます。
</Solution>
</Exercise>

## 参考文献

- J. C. Lagarias, "The 3x+1 problem and its generalizations", *American Mathematical Monthly* 92 (1985), 3–23. — この問題の標準的な入門サーベイ。歴史的経緯と主要結果がまとまっています。
- J. C. Lagarias (ed.), *The Ultimate Challenge: The 3x+1 Problem*, American Mathematical Society, 2010. — 上のサーベイを含む論文集。現在の到達点を知るならまずこれです。
- R. Terras, "A stopping time problem on the positive integers", *Acta Arithmetica* 30 (1976), 241–252. — 停止時間が有限な自然数の密度が $1$ であることの原論文。
- I. Krasikov and J. C. Lagarias, "Bounds for the 3x+1 problem using difference inequalities", *Acta Arithmetica* 109 (2003). — $x$ 以下で $1$ に到達する数の個数の下界。
- T. Tao, "Almost all orbits of the Collatz map attain almost bounded values", arXiv:1909.03562 (2019). — 確率的直観を厳密化した現時点で最強の結果。
- D. Barina, "Convergence verification of the Collatz problem", *The Journal of Supercomputing* 77 (2021). — $2^{68}$ までの計算機検証。
- J. H. Conway, "Unpredictable iterations", *Proceedings of the 1972 Number Theory Conference*, University of Colorado, 1972. — 一般化コラッツ写像の決定不能性。

## Appendix: 手を動かすためのヒント

**自分で実験するときの注意。** 第 3 節のコードは素朴な実装なので、$10^7$ を超えるあたりから遅くなります。速くするには、<Ref to="exr-orbit-of-seven" /> の解答で触れたメモ化（一度計算した数の手数を辞書に保存する）を入れるのが定石です。ただし辞書が巨大になるので、「$n$ 未満の値に落ちたら打ち切る」方式（つまり停止時間 $\sigma(n)$ だけを計算し、<Ref to="thm-equivalent-stopping" /> に頼る）のほうがメモリ効率は良くなります。

**見つけても喜びすぎないこと。** 「反例を見つけた」と思ったときは、まず桁あふれを疑ってください。C 言語や Java の 64 ビット整数は $9.2 \times 10^{18}$ 程度で溢れます。$27$ が $9232$ まで登ったように、コラッツ軌道は出発点の何桁も上まで行くので、$10^{18}$ 台の数を試すと途中で簡単に溢れます。Python の整数は自動的に多倍長になるので、この点では安心です。

**それでも挑戦したい人へ。** この記事で見たとおり、素朴な確率的議論は $3n-1$ 版（<Ref to="prop-3n-minus-1" />）を排除できず、剰余類による議論は <Ref to="rem-terras" /> の壁を越えられません。新しい証明は、$+1$ という項が正の整数の世界で果たしている特別な役割を掴まえるものでなければならないはずです。それが何なのかは、まだ誰も知りません。数学の問題がなぜ難しくなるのかについては [数学はなぜ難しいのか](/mathematics/math-columns/why-math-is-hard) も参考にしてください。計算機に大きく頼って解決した例としては [四色定理](/mathematics/math-columns/four-color-theorem)（<Ref to="mathematics/math-columns/four-color-theorem#thm-four-color" />）が対照的で、こちらは「有限個の場合に帰着できた」こと（<Ref to="mathematics/math-columns/four-color-theorem#def-configuration" text="不可避集合と可約配置" />）が決め手でした。コラッツ予想には、その有限化の手段がまだ見つかっていないのです。