コラッツ予想の証明
Proof of the Collatz Conjecture
加藤 一郎

Ichiro KATO
e-mail : kato@my.zaq.jp

要約
数論の未解決問題として知られているコラッツ予想とは、任意の正の整数を、その偶奇に応じて 2 で除算する、あるいは 3 倍して 1 加算するという処理を繰り返すと、最終的には必ず 1 に到達するという予想である。本稿は、この処理プロセスが奇数から奇数への変換と等価であることを示し、その逆変換にて考察を加えることで証明を試みるものである。変換内容を定式化することで、その継続性・稠密性・非循環性・一意性を検証し、この変換が整数 1 からすべての正の奇数に到達可能であることを示す。
キーワード : コラッツ予想、逆変換、剰余判定、継続性、非循環性、稠密性、一意性

Keywords : Collatz conjecture, inverse transform, remainder judgment, continuity, acyclicity, denseness, uniqueness１. はじめにコラッツ予想とは、以下の内容である。
任意の正の整数に対し、以下で定義される関数 f (x) を繰り返し適用すると、いずれ 1 になる。
x/2

( x ≡ 0 (mod 2) )3x+1

( x ≡ 1 (mod 2) )f (x) =

本稿は、以下のアイディアを結び付けるとこで、この予想が正しいことを証明するものである。
 コラッツの変換ルールを、「奇数から奇数への変換」に単純化
 「6 の剰余に基づく分類モデル」を導出し、コラッツ変換を算術比と幾何比で構成された数式で整理
 「変換内容の相関図」を作画し、不規則に変動するコラッツ変換の背後に存在する規則性や周期性を可視化
 1 から任意の奇数に到達する「逆演算のアプローチ」

２. 奇数変換プロセスの定義与えられた任意の整数が奇数の場合は 3 倍して 1 が加算されてその結果は必ず偶数になる。そして、偶数の場合は奇数に達するまで 2 で割り続ける。したがって、コラッツ予想のプロセスは 「奇数を 3 倍して 1 を加算し、得られた偶数が奇数に到達するまで 2 で割り続ける」 という一連の処理を繰り返すことに他ならない。
以上より、このプロセスは 「奇数 P から奇数 Q への変換を繰り返す」 手続きであるとみなすことができる。このプロセスを、ここでは仮に 「PQ 変換」 と呼ぶ。なお、初期値が偶数の場合は、割り切れる最大の 2 のべき乗で除算し、あらかじめ奇数にしておく。PQ 変換にてコラッツ予想のプロセスを表現すると以下のようになる。
「任意の正の奇数に PQ 変換を繰り返し適用すると、いずれ 1 になる」
例として、9 から始まるプロセスを挙げておく。
まず通常のプロセスの場合は以下のようになる。（ → 3 倍して 1 加算する処理、 ⇒ 2 で除算する処理 ）9 → 28 ⇒ 14 ⇒ 7 → 22 ⇒ 11 → 34 ⇒ 17 → 52 ⇒ 26 ⇒ 13 → 40 ⇒ 20 ⇒ 10 ⇒ 5 → 16 ⇒ 8 ⇒ 4 ⇒ 2 ⇒ 1-1-

これを PQ 変換で表記すると以下のようになる。
9 → 7 → 11 → 17 → 13 → 5 → 1

変換前の奇数を P、変換後の奇数を Q、割り切れる最大の 2 のべき乗を 2m とすれば、PQ 変換は以下のように表現できる。
Q( 3P + 1 ) / 2m=…①

PQ 変換は、以下の性質を持つ
 P が奇数であるため 3P + 1 は必ず偶数となり、少なくとも 2 で一回除算できる。したがって、m は 1 以上の整数である。
 異なる P であっても、 2m で除算した結果、同一の Q を得る場合がある。すなわち PQ 変換は n : 1 の対応関係を持つ。
また、以下の定理が成り立つ。
定理 1 : 変換結果 Q が P と等しくなるのは P = 1 の場合のみである。
∵

Q = P となる奇数を x とおき、①式に代入すると
x= ( 3x + 1 ) / 2m

これを x で解くと
x

= 1 / ( 2m - 3 )x が正の奇数(整数)であるという条件を満たす m は 2 のみであることは自明である。
m = 2 を代入すると x は 1 となる。すなわち P = 1 の場合のみ Q = P となる。

３. ＰＱ変換の定式化
任意の奇数 P が与えられた際、3 倍して 1 加算した時点で、その値を除算可能な最大の 2m が存在する。この時の P と m の関係について分析する。今、g を偶数、k を奇数、n をゼロ以上の整数とし、奇数 Y を次の式で表現してみる。
Y =gn + k…②

係数 g の値が大きいほど表現できる奇数 Y の密度は低くなり、初期値 k の値が大きいほど前半の奇数が排除される。一般の奇数表現 2n + 1 は、g, k それぞれの最小値を採用しており、これですべての奇数を網羅している。この②式の奇数表現を利用して、ＰＱ変換で扱われる奇数の条件を満たす最小の g, k 値を求めることで、PQ 変換を定式化する。
今、②式の形式で P が与えられているとし、①式の P に②式の右辺を代入し、n に対して整理する。
Q=( 3P + 1 ) / 2m=

( 3( gn + k ) + 1 ) / 2m=

( 3g / 2m )⋅n + ( 3k + 1 ) / 2m

ここで、Q も奇数であることから再び②式の表現を適用すると、g, k の条件から右辺第一項の n の係数は偶数であり、右辺第二項は奇数でなければならない。
3g / 2m≡ 偶数…③( 3k + 1 ) / 2m

≡ 奇数

…④

このそれぞれの式から、g, k の最小値を求める。まず③式 g の最小値を求める。Q は奇数(すなわち整数)であるため、分子である 3g は 2m の因数を持つ必要がある。更に 2m で約分した結果、③式そのものが偶数であるためには、g は 2⋅2m の因数を持たなければならない。この条件を満たす最小の g 値は、2⋅2m そのものであることは自明である。すなわち、
g =2(m+1)…⑤-2-

次に、④式 k の最小値を求める。Q は奇数すなわち整数であるため、分子である 3k+1 は 2m の因数を持つ奇数でなければならない。今 R を任意の奇数とすると、以下が成り立つ。
3k + 1=R⋅2m

これを k で解くと、(R⋅2m - 1 ) / 3

k =

…⑥

k の最小値を求めることは、奇数 R の最小値を求めることに他ならない。ここで、以下の定理を準備する。
定理 2 : m を偶数とすれば、メルセンヌ数 2m - 1 は 3 の倍数であり、3 での除算結果は奇数となる。
∵

m が偶数のメルセンヌ数は、２進法で偶数個の１が並ぶレプユニットとなる。２進法では、奇数桁と偶数桁の１の個数差が 3 の倍数である時、その値は 3 の倍数である。この場合、奇数桁と偶数桁の個数は一致することから、3 の倍数となる。またもし、3 の除算結果が偶数であるとすると元のメルセンヌ数も偶数でなければならないが、2m - 1 が奇数であることは自明であり、よって 3 の除算結果は奇数となる。

⑥式 R の最小値を求めるため、m の偶奇で場合分けを行う。m が偶数の場合、R = 1 をとれば⑥式はメルセンヌ数そのものとなり、上記定理 2 より 3 で割り切れその結果は奇数となる。したがって、R = 1 が最小の k といえる。
対して、m が奇数の場合は、R が 1 あるいは 3 では⑥式は整数にならず、R = 5 においてようやく整数化される。よって、m が奇数の場合、k を最小とする R は 5 となる。以下、R が 5 の場合、すべての奇数 m で k が奇数となることを検証しておく。
k=( R⋅2m - 1 ) / 3=( 5⋅2m - 1 ) / 3=( 3⋅2m + 2(m+1) - 1 ) / 3=

2m + ( 2(m+1) - 1 ) / 3

第一項は偶数であり、第二項は定理 2 より奇数となる。よってすべての奇数 m で k が奇数となることが確認できた。
以上より、⑥式は m の偶奇で仕分けされ、以下のようになる。

k( 2m - 1 ) / 3( m ≡ 0 (mod 2) )( 5⋅2m - 1 ) / 3( m ≡ 1 (mod 2) )=…⑦⑤⑦の結果を②式に代入してまとめると、奇数 P は以下のように表現できる。

Pn⋅2(m+1) + ( 2m - 1 ) / 3( m ≡ 0 (mod 2) )n⋅2(m+1) + ( 5⋅2m - 1 ) / 3( m ≡ 1 (mod 2) )=…⑧

さらに、⑧式を①式に代入すると、2m で除算した結果の Q を求めることができる。

Q=

6n + 16n + 36n + 5( m ≡ 0 (mod 2) )( N/A )( m ≡ 1 (mod 2) )

…⑨

-3-

４. ＰＱ相関図
検討の見通しをよくするため、⑧⑨の結果を用いて PQ 相関図を作画する。PQ 相関図とは、横軸に奇数 P を、縦軸に奇数 Q
をとり、その変換に関与する 2 のべき乗数 m を、黒丸数字で各交点に与えた２次元グラフである。奇数 Q を 6 で除算すると、1,
3, 5 の３通りの剰余が得られる。この剰余と商を奇数分類のパラメータ S, n として縦軸に添えておく。

8

7

6

5

4

3

2

1

0

5

53

3

51

1

49

5

47

3

45

1

43

5

41

3

39

1

37

5

35

3

33

1

31

5

29

3

27

1

25

5

23

3

21

1

19

5

17

3
1

15
13

5

11

3

9

1

7

5

5

3

3

1

1

n S Q
P

➊
❷

➊
❷

➊
P=Q

❷

➊
m=1

❷

➊
❷

➊
❷

➊

❶
❷
1

5

➍

➌
m=4

➍

❸

➍
3

➌
m=3

❷

➊
❷

➌

m=2

❻
7

9

11

13

15

17

19

21

❺

m=5
m=6
23

25

27

29

31

33

35

37

39

41

43

45

47

49

51

53

55

57

59

61

63

図 1 ： PQ 相関図
黒丸の位置で、PQ 変換が成立する P 値(横軸)と Q 値(縦軸)を求めることができる。黒丸内の数字は変換時の 2 のべき乗数である。

この PQ 相関図により、以下の PQ 変換特性を確認することができる。
 PQ 変換は n : 1 であるため、P 列上には一か所だけ m が存在し、Q 行上には複数の m が存在する。


式①において、P 値が与えられるとそれに対応した最大値 m も確定するため、Q 値が一意に決まる。
一方、1 つの Q 値に対して P と m の組が複数存在するため、Q 値に対応した複数の P 値が存在する。

 同値の m は、右上がりの傾きを持った半直線上に、等間隔で並ぶ。


式⑧において、m を固定し n を序数とした際、等差数列の一般式となる。

 S = 1 の Q 行上の m は偶数、S = 5 の Q 行上の m は奇数であり、それらは等比間隔で並ぶ。


式⑧において、n を固定し m を序数とした際、等比数列の一般式となる。

 S = 3 の Q 行上には、該当する m は 1 つも存在しない。


式⑨において、Q = 6n + 3 に対応する P は存在しない。

 45°の破線ライン（P = Q）上にある m 点は、原点（P = Q = 1）に存在する m = 2 のみである。


これは、定理 1 を裏付けている。

 PQ 変換で値が増加するのは、P = Q ラインよりも上部の領域にある m = 1 の変換時のみである。

-4-

65

67

69

71

５. 逆変換プロセスの定義
PQ 変換に対し、Q に至った元の P に遡る逆プロセスを考える。この逆変換を、ここでは 「QP 変換」 と呼ぶ。QP 変換を利用することで、コラッツ予想の命題は以下のように表現できる。
「1 から開始してＱＰ変換を有限回適用すれば、任意の正の奇数に到達できる」①式を P について解くと、QP 変換の変換式が得られる。
( 2m⋅Q - 1 ) / 3

P =

…⑩

⑩式の右辺は、3 の除算となっているため、P が奇数であるためには分子部分は 3 の倍数でなければならない。すなわち、与えられた Q に対して取りうる m の値は制限されている。⑩式に⑨式を代入することで、その制約条件は m の偶奇により与えられる
ことがわかる。なお、Q = 6n + 3 の場合は条件を満たす m が存在しないため除外する。

P( 2m⋅(6n + 1) - 1 ) / 3( ここで、m = 2, 4, 6, 8, … )( 2m⋅(6n + 5) - 1 ) / 3( ここで、m = 1, 3, 5, 7, … )=…⑪

QP 変換は 1 : n の関係であるため、1 つの Q 値から複数の P 値が生成される。生成された各 P 値を次の Q 値として新たな P値を求めることを繰返すため、QP 変換は階層的なツリーを形成する。なお、6 の剰余が 3 に到達した場合は新たな階層の枝は延びず、その枝の変換プロセスは停止する。例として１から展開した数段のツリー図を挙げておく。

初期Ｑ値

Ｐ値

Ｐ値

Ｐ値

次のＱ値

次のＱ値

次のＱ値

3

1

5
1

N/A

13

69

53

277

213

21
N/A

141

113
453

N/A

35
N/A

85

17

N/A

565
N/A

図 2 ： QP 変換トレース時のツリー構造
任意の Q 値から複数の P 値が導出され、それが新たな Q 値となり階層的に展開が進む。1 つの Q 値から無数の P 値が生成されるため、破線にてそれを表現している。一方、1 つも P 値を導出しない Q 値(N/A)も存在する。なおＰ値 1 は、例外的にルート間を無限に循環する。

６. ＱＰ変換の継続性
1 を初期値として QP 変換を有限回繰り返すことで任意の奇数に到達するには、QP 変換で形成されるツリーが停止することなく無限に階層展開されることが保証されなければならない。QP 変換には P 値の導出タイプが３種類あり、それは与えられた Q 値の 6 の剰余 S によって分類される。S = 1 および S = 5 の場合は複数の P 値が生成される。前者は 2 の偶数べき乗が関与し、後者は 2 の奇数べき乗が関与する。そして、S = 3 の場合は P 値の導出は起こらず階層展開はそのノードで停止する。もし、あらゆる階層で S = 3 のノードが一斉に発生すると、QP 変換のツリーはその時点で停止してしまうことになる。このような事態に陥らないこと検証するために、P 値を導出する式⑪の周期性を確認する。

-5-

ここで、分析の見通しを良くするために周期表記 T を定義する。今、序数 j の増加に応じて変化する値を d1, d2, d3, … とする。
序数が i + 1 番目になった時、1 番目の序数に対応した値 d1 に戻り、以降周期的に同じ値が繰り返される場合、この周期状態を以下のように表す。
T( j : d1, d2, d3, … , di )この表記法の具体例をいくつか示しておく。
T( u : 1, 2, 3, 4, 0 )……

自然数 u ( 1, 2, 3, … ) の 5 の剰余T( v : 2, 1, 0 )……

偶数 v ( 2, 4, 6, 8, … ) の 3 の剰余T( w : 1, 3 )……

奇数 w ( 1, 3, 5, 7, … ) の 4 の剰余

まず、式⑪において m が偶数の場合の周期性を分析する。P を n と m の関数と捉え、処理を容易にするため変形する。
P(n,m)=( 2m⋅(6n + 1) - 1 ) / 3=2n⋅2m + (2m - 1 ) / 3

ここで両辺に 6 の剰余をとり、P 値の 6 の剰余を Pt と表記する。周期表記 T を使って右辺を整理することで、Pt の周期性を確認する。なお、右辺第二項を周期表記に置換するにあたり、定理 2 を活用した。
Pt(n,m) =( 2n⋅2m + ( 2m - 1 ) / 3 ) mod 6=( ( 2n⋅2m mod 6 ) + ( ( 2m - 1 ) / 3 mod 6 ) ) mod 6=( ( ( 2n mod 6 )⋅(2m mod 6 ) ) mod 6 + T( m: 1, 5, 3 ) ) mod 6=( ( T( n: 0, 2, 4 )⋅T( m: 4 ) ) mod 6 + T( m: 1, 5, 3 ) ) mod 6=( T( n: 0, 2, 4 ) + T( m: 1, 5, 3 ) ) mod 6

m が奇数の場合も同様の処理を式⑪に対して行い、偶奇各々で得られた結果をまとめると以下のようになる。

Pt(n,m)( T( n: 0, 2, 4 ) + T( m: 1, 5, 3 ) ) mod 6( ここで、m = 2, 4, 6, 8, … )( T( n: 2, 0, 4 ) + T( m: 1, 5, 3 ) ) mod 6( ここで、m = 1, 3, 5, 7, … )=…⑫以上、⑫式により、m の偶奇を問わず、P 値の 6 の剰余は周期的に３値をとることが示された。この周期性のイメージを確認する
ため実際の値のサンプルを表 1 に与える。周期性が確認しやすいように m の偶奇で別表とした。与えられた Q 値から導出される P 値を各行に列挙し、S = 1, 3, 5 で各セルの背景色を区別している。なお、S = 3 は P 値の導出が不可能となる Q 値である。
S=1
S=5
S = 3 (N/A)

表 1 ： 導出される P 値の周期性
QP 変換により生成される P 値は、序数 m に対して S = 1,5,3 の周期性を持っている。
m ≡ 偶数

S=1m ≡ 奇数

S=5

n

Q

2

4

6

8

10

12

n

Q

1

3

5

7

9

11

0

1
7
13
19
25
31
37
43
49
55
61
67
73

1
9
17
25
33
41
49
57
65
73
81
89
97

5
37
69
101
133
165
197
229
261
293
325
357
389

21
149
277
405
533
661
789
917
1045
1173
1301
1429
1557

85
597
1109
1621
2133
2645
3157
3669
4181
4693
5205
5717
6229

341
2389
4437
6485
8533
10581
12629
14677
16725
18773
20821
22869
24917

1365
9557
17749
25941
34133
42325
50517
58709
66901
75093
83285
91477
99669

0

5
11
17
23
29
35
41
47
53
59
65
71
77

3
7
11
15
19
23
27
31
35
39
43
47
51

13
29
45
61
77
93
109
125
141
157
173
189
205

53
117
181
245
309
373
437
501
565
629
693
757
821

213
469
725
981
1237
1493
1749
2005
2261
2517
2773
3029
3285

853
1877
2901
3925
4949
5973
6997
8021
9045
10069
11093
12117
13141

3413
7509
11605
15701
19797
23893
27989
32085
36181
40277
44373
48469
52565

1
2
3
4
5
6
7
8
9
10
11
12

1
2
3
4
5
6
7
8
9
10
11
12

-6-

トレースが停止するのは、6 の剰余が 3 になる場合のみであり、これは 3 回に 1 回現れる。その他 2 回現れる剰余 1 および剰余5 の場合は、それを新たな Q 値としてトレースの続行が可能である。したがって QP 変換は停止することなく、継続して無限のト
レースが可能であることが示された。

７. ＱＰ変換の非循環性
1 を初期値として QP 変換を有限回繰り返すことで任意の奇数に到達するには、途中で循環プロセス、すなわち一般的に言う
無限ループに陥らないことが必要条件となる。QP 変換が無限ループを起こす場合は、(Ⅰ) Q と P が同値となる変換が存在する(Ⅱ) 変換された P が、それ以前の変換で生じたいずれかの P と等しいのいずれかが満たされた場合である。
まず(Ⅰ)の場合を検討する。Q = 1 の場合には、その複数の枝の内の 1 つに P = 1 の枝が存在するため(Ⅰ)の条件に合致するが、1 は最終到達値であるため例外的に許される。一方、定理 1 により Q = P となるのは P = 1 の場合のみであり、Q > 1 の領域
で Q = P となる変換は存在しないことは自明である。PQ 相関図の P = Q のライン上の変換点 m が、原点（Q = P = 1）以外に存在しないこともそれを裏付けている。
次に(Ⅱ)の場合を検討する。今までの議論により、QP 変換によって Q 値から導出される P 値には以下の禁則が成り立つ。
(禁則 1) 導出された P 値は、元の Q 値とは異なる値となる。（ただし特異点となる P = 1 を除く）
(禁則 2) 異なる Q 値から同一の P 値は導出されない。
これらの禁則を PQ 相関図上の概念図で示す。

Q
Q

導出不能
Q1

P

導出不能
P1

P2

P3

図 3 ： PQ 相関図における P 値の禁則
Q1 から導出された P1 が、導出元の Q1 と等しい値になることはない。
Q1 から導出された P3 と同じ値が、他の Q 値である Q2 から導出されることはない。

これら禁則の条件下では、あるノードがツリー途中の既に導出されているノードに戻るような循環は起こり得ず、唯一ルートノードに戻る循環の可能性だけが残る。しかしルート値を 1 に限定すると、導出される P 値がルート値 1 に戻る局面は、変換元の Q
値自体が 1 の場合のみであり、これは特異点として除外される。
したがって、1 をルート値とする QP 変換ツリーは、綿々と新たな P 値を導出し続けることになる。その際、一度導出された P 値
は別のノードで出現することはなく、結果としてすべてのノードが異なる値を持つ。

-7-

一方、無限ループを形成するには、同一の値を持つノードがツリー上に少なくとも 1 組は存在する必要がある。よって、QP 変換
は、特異点(Q = P = 1)を除いて、無限ループを生じないことが確認できた。

８. ＱＰ変換の稠密性
今、1 を除く任意の奇数 P が与えられたとき、その P に①式で与えられる PQ 変換を施すことで、その P 値とは異なる値の奇数
Q が 1 つ生成される。このことは、すべての奇数 P が Q と紐づいていることに等しい。この紐づけをＱＰ変換のツリーの枝として捉えると、ノードとなる P は必ずなんらかのツリーの一部に属しており、単独では存在しないことを示している。すなわちＱＰ変換が関与する対象は、自然数に含まれるすべての奇数を網羅していることが確認できる。

９. ＱＰ変換の一意性
ツリーにはルートが存在するが、そのルート値に PQ 変換を施した場合は、そのルート自身の値に戻る循環性を持っていなければならない。なぜなら、もしルート値の変換結果が異なる値であった場合、その変換結果が本来のルートとなるからである。
もし奇数集合の中に複数の独立したツリーが存在するとすれば、各ツリーはそれぞれ異なる値のルートを持っていることになる。
しかし定理 1 で示したとおり、PQ 変換で循環性を持つのは P = 1 のみである。よって QP 変換のツリーは 1 をルート値とする 1
つのツリーのみ存在し、他のルート値を持つ独立したツリーは存在しない。
更に、到達可能なすべての奇数は、このツリーの配下に存在していることになる。なぜならば、もしこのツリー配下に含まれない
奇数があった場合、その奇数は別の独立したツリー内に存在することとなり、1 つのツリーのみ存在するという結論と矛盾するためである。

１０. まとめ
ここまでの検証により、QP 変換において以下の結果が得られた。
 継続性： ツリーのトレースは無限に継続可能で停止しない 非循環性： ツリーのトレース過程で無限ループは発生しない

 稠密性： すべての奇数はなんらかのツリーに属している

 一意性： ツリーは 1 つのみ存在する

これらをまとめると、QP 変換においては 1 をルートとしたツリーが 1 つだけ存在しており、そのツリーは停止することも循環することもなく、すべての奇数をノードとして包含していることが導かれる。よって、1 を初期値として QP 変換を有限回繰り返すことで任意の奇数に到達可能であり、この処理を逆に辿れば、任意の奇数から有限回の PQ 変換によって必ず 1 に到達することになる。
これにより、コラッツ予想の正しさが証明された。

-8-