コラッツの予想 Collatz Problem

　コラッツの予想 (Collatz Problem)

コラッツの予想 (Collatz Problem) は角谷の予想 (Kakutani's problem) とも呼ばれています。

コラッツの予想

自然数 n に対して、n が奇数なら３かけて１加える。偶数なら２で割る。以上の操作を繰り返すと、全ての自然数に関して、最終的に、１→４→２→１のループに入る。

　つまり

１→４→２→１

２→１

３→１０→５→１６→８→４→２→１

４→２→１　

５→１６→８→４→２→１

６→３→１０→５→１６→８→４→２→１

７→２２→１１→３４→１７→５２→２６→１３→４０→２０→１０→５→…

８→４→２→１

９→２８→１４→７→…

といった感じです。何となく、いずれ１に帰着し、ループに入りそうな気がしますねえ。

しかし、証明はと言うと、未だ解決されていません。この問題に決着を付けるためには、証明するか、反例を見つけるかどちらかですね。反例はと言うと、

・充分この操作を続けたあとも、元の数、n 以下になることがない数。

・１→４→２→１以外のループをつくる数。

のどちらかですね。

未だに解決されていない問題を解こうなんておこがましいことは考えませんが、少しだけ考えてみましょう。

任意の自然数を n とします。

n が奇数の場合、３かけて１たすわけですが、この操作のあとにできる自然数は必ず偶数です。つまり３かけて１たす操作に２で割る操作は付き物というわけですね。

というわけで次のようにあらわすことができます。

t1 (任意の自然数)

tn+1 =　　 ( 3tn + 1 )/2 　{ tn ≡ 1(mod 2)}

　　　　　　tn /2　　　　　 { tn ≡ 0(mod 2)}

このとき tn はいずれ（１、２）のループにはいる。

t1 を負の数まで拡張すると、

(-1)

(-5、-7、-10)

(-17、-25、-37、-55、-82、-41、-61、-91、-136、-68、-34)

のループがあることが知られています。

話を自然数に戻しましょう。

ここで、2ⁿ から　2ⁿ⁺¹-1 までの自然数の集合をAnとします。

A1∪A2∪A3∪…∪An

に含まれる全ての自然数について、証明できたと仮定します。そこでAn+1を考えます。

An+1 { 2ⁿ⁺¹、2ⁿ⁺¹+1、2ⁿ⁺¹+2、2ⁿ⁺¹+3、2ⁿ⁺¹+4、…、2ⁿ⁺²-3、2ⁿ⁺²-2、2ⁿ⁺²-1}

この集合の中で偶数だけを取り出してやると、

{ 2ⁿ⁺¹、2ⁿ⁺¹+2、2ⁿ⁺¹+4、…、2ⁿ⁺²-4、2ⁿ⁺²-2}

となりますね。これは次の操作で２で割るわけですがそうしてできた集合、

{ 2ⁿ、2ⁿ+1、2ⁿ+2、…、2ⁿ⁺¹-2、2ⁿ⁺¹-1}

は、集合Anと一致しますので、集合An+1の偶数に関しては成立することが分かります。

問題は奇数なのです。

これから先の方針としては、この残りの奇数が数回の操作の後、2ⁿ⁺¹-1以下（少なくとも2ⁿ⁺²-1)になるか、2のべき乗になるようにしてみようと思います、無理だろうけど。

ではまず集合An+1から奇数だけを取り出してきます。

Bn { 2ⁿ⁺¹+1、2ⁿ⁺¹+3、2ⁿ⁺¹+5、2ⁿ⁺¹+7、…、2ⁿ⁺²-5、2ⁿ⁺²-3、2ⁿ⁺²-1}

これらの全ての要素は、次の操作で３かけて１たすわけですね。

{ 3・2ⁿ⁺¹+4、3・2ⁿ⁺¹+10、3・2ⁿ⁺¹+16、3・2ⁿ⁺¹+22、…、3・2ⁿ⁺²-14、3・2ⁿ⁺²-8、3・2ⁿ⁺²-2}

さらに２で割ります。

{ 3・2ⁿ+2、3・2ⁿ+5、3・2ⁿ+8、3・2ⁿ+11、…、3・2ⁿ⁺¹-7、3・2ⁿ⁺¹-4、3・2ⁿ⁺¹-1}

この集合の要素で偶数は交互にあらわれるので２で割ります。

{ 3・2^n-1+1、3・2ⁿ+5、3・2^n-1+4、3・2ⁿ+11、…、3・2ⁿ⁺¹-7、3・2ⁿ-2、3・2ⁿ⁺¹-1}

ここにきて集合An+1の奇数、集合Bnの中で３倍して１足したあと、４で割った要素が出てきました。

つまり元の奇数を(2ⁿ⁺¹+4m+1)型と(2ⁿ⁺¹+4m+3)型に分類すると、(2ⁿ⁺¹+4m+1)型は３倍して１足すと、(3・2ⁿ⁺¹+12m+4)となり４で割って(3・2^n-1+3m+1)となります。

この場合、元の奇数を x (= 2ⁿ⁺¹+4m+1) とおくと

( 3x + 1 )/4

となったことになります。

x - ( 3x + 1 )/4 = ( x - 1)/4 = ( 2ⁿ⁺¹ + 4m + 1 - 1)/4 > 0

なので元の数、x よりかは小さくなっているのが分かります。少なくとも2ⁿ⁺²-1よりかは小さい値です。集合Bnの中でのみのループをつくらない限りはこれも成立します。ここでは、これは無視して話を進めていきましょう。

残りは、(2ⁿ⁺¹+4m+3)型の奇数のみです。

(2ⁿ⁺¹+4m+3)型の奇数は具体的に次のような感じです。（(2ⁿ⁺¹+4m+3)型の奇数は赤で、２のべき乗になった時点で青であらわしています。）

３→１０→５→１６→８→４→２→１

７→２２→１１→３４→１７→５２→２６→１３→４０→２０→１０→５→１６→８→４→２→１

１１→３４→１７→５２→２６→１３→４０→２０→１０→５→１６→８→４→２→１

１５→４６→２３→７０→３５→１０６→５３→１６０→８０→４０→２０→１０→５→１６→８→４→２→１

１９→５８→２９→８８→４４→２２→１１→…（１１参照）

２３→…（１５参照）

２７→（１１１回の操作で１に）

３１→（１０６回の操作で１に）

３５→（１５参照）

３９→１１８→５９→１７８→８９→２６８→１３４→６７→２０２→１０１→３０４→１５２→７６→３８→１９→（１９参照）

やはりちょっと複雑なものが多そうです。

前にも述べましたように最終的に１になるまえに２のべき乗になります。最初の数が２のべき乗でない限りは、途中の操作で、ある奇数を３倍して１足せば、２のべき乗になるということが必ず起こるはずである。

上の例で言えば、奇数５を３倍して１足せば１６になり、めでたく２のべき乗になったわけです。

そこで、このような数を考えてみましょう。

（ある奇数）× 3 + 1 = 2^k

となる（ある奇数）はどのような奇数でしょうか？

上に示された５は赤ではなく黒で書かれています。つまり(2ⁿ⁺¹+4m+1)型です。ちなみに(2ⁿ⁺¹+4m+3)型でもあり得ることなのか考えてみます。

(2ⁿ⁺¹+4m+3) × 3 + 1 = 2^k

3・2ⁿ⁺¹ + 12m + 10 = 2^k

3・2ⁿ + 6m + 5 = 2^k-1

左右両辺の各項を見てみると、n = 0 にならなければならない。（ k = 1 なら左辺のいずれかの項は負の数にならなければならないため。）

3・2⁰ + 6m + 5 = 2^k-1

6m + 6 = 2^k-1

左辺は３の倍数だが右辺は２のべき乗なので矛盾する。

よって最終的に２のべき乗になる前は必ず(2ⁿ⁺¹+4m+1)型の奇数を通過する。

なかなか見えてきませんねえ。ここでどういう数を選ぶと１に辿り着くのに苦労するかを見ていきましょう。

下の表は１に辿り着くまでの操作の回数を示したものです。

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
0	1	7	2	5	8	16	3	19	6	14	9	9	17	17	4	12	20	20	7
21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40
7	15	15	10	23	10	111	18	18	18	106	5	26	13	13	21	21	21	34	8
41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60
109	8	29	16	16	16	104	11	24	24	24	11	11	112	112	19	32	19	32	19
61	62	63	64	65	66	67	68	69	70	71	72	73	74	75	76	77	78	79	80
19	107	107	6	27	27	27	14	14	14	102	22	115	22	14	22	22	35	35	9
81	82	83	84	85	86	87	88	89	90	91	92	93	94	95	96	97	98	99	100
22	110	110	9	9	30	30	17	30	17	92	17	17	105	105	12	118	25	25	25
101	102	103	104	105	106	107	108	109	110	111	112	113	114	115	116	117	118	119	120
25	25	87	12	38	12	100	113	113	113	69	20	12	33	33	20	20	33	33	20
121	122	123	124	125	126	127	128	129	130	131	132	133	134	135	136	137	138	139	140
95	20	46	108	108	108	46	7	121	28	28	28	28	28	41	15	90	15	41	15
141	142	143	144	145	146	147	148	149	150	151	152	153	154	155	156	157	158	159	160
15	103	103	23	116	116	116	23	23	15	15	23	36	23	85	36	36	36	54	10
161	162	163	164	165	166	167	168	169	170	171	172	173	174	175	176	177	178	179	180
98	23	23	111	111	111	67	10	49	10	124	31	31	31	80	18	31	31	31	18
181	182	183	184	185	186	187	188	189	190	191	192	193	194	195	196	197	198	199	200
18	93	93	18	44	18	44	106	106	106	44	13	119	119	119	26	26	26	119	26

２７や３１や４１などは数が小さいにもかかわらず、大変な作業が必要であることがよく分かります。

また、例えば１２と１３、１４と１５、１８と１９、２０と２１、２２と２３など連続する２数で手続きの回数が同じであるケースが目につきます。

次にある自然数 n が１に辿り着くまでにとる最高の値を表に示します。

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
1	2	16	4	16	16	52	8	52	16	52	16	40	52	160	16	52	52	88	20
21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40
64	52	160	24	88	40	9232	52	88	160	9232	32	100	52	160	52	112	88	304	40
41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60
9232	64	196	52	136	160	9232	48	148	88	232	52	160	9232	9232	56	196	88	304	160
61	62	63	64	65	66	67	68	69	70	71	72	73	74	75	76	77	78	79	80
184	9232	9232	64	196	100	304	68	208	160	9232	72	9232	112	340	88	232	88	808	80
81	82	83	84	85	86	87	88	89	90	91	92	93	94	95	96	97	98	99	100
244	9232	9232	84	256	196	592	88	304	136	9232	160	280	9232	9232	96	9232	148	448	100
101	102	103	104	105	106	107	108	109	110	111	112	113	114	115	116	117	118	119	120
304	232	9232	104	808	160	9232	9232	9232	9232	9232	112	340	196	520	116	352	304	808	160
121	122	123	124	125	126	127	128	129	130	131	132	133	134	135	136	137	138	139	140
9232	184	628	9232	9232	9232	4372	128	9232	196	592	132	404	304	916	136	9232	208	628	160
141	142	143	144	145	146	147	148	149	150	151	152	153	154	155	156	157	158	159	160
424	9232	9232	144	9232	9232	9232	148	448	340	1024	152	520	232	9232	156	472	808	9232	160
161	162	163	164	165	166	167	168	169	170	171	172	173	174	175	176	177	178	179	180
9232	244	736	9232	9232	9232	9232	168	4372	256	9232	196	520	592	9232	176	532	304	808	180
181	182	183	184	185	186	187	188	189	190	191	192	193	194	195	196	197	198	199	200
544	9232	9232	184	628	280	952	9232	9232	9232	4372	192	9232	9232	9232	196	592	448	9232	200

ここである自然数 n が操作中にとる最高の値 Sn を n の関数 f(n) としてあらわせるとします。そうすると有限回の操作の後に、１に辿り着くか、（１→４→２→１）以外のループを形成します。

また Sn を次のようにあらわすことができてもいいわけです。

Sn ≦ f(n)

このような f(n) をさがして、Sn 以下でのループは（１→４→２→１）のみであることを示せばいいですね。

続く

＜別の観点から…＞

１から2nまでのすべての自然数は最終的に１に帰着するとします。ここで奇数 (2n+1) は無限回の操作後も１にならないとします。このとき、(2n+1) は、その過程で 2n 以下とはなり得ず（なれば必ず１に帰着するので）、途中でループを形成するか発散します。ループを形成しないとすると、その過程であらわれたすべての数は発散することになります。つまり発散する数は n 以上で無限に存在することになります。しかしその中に２のべき乗である数は含みません。また (1から2nのいずれか)×(2のべき乗) のかたちにもなりません。下図参照。

｛１、２、３、…、2n-1、2n｝

はすべて１に帰着。2n+1が発散すると考えると、

2n+1 → 3(2n+1)+1 → {3(2n+1)+1}/2 → … 　　　　　…(*)

の過程であらわれる数はすべてが 2n 以下にはならず、発散する。または途中でループを形成。

{3(2n+1)+1}/2 = 3n+2

これが偶数(つまり n が偶数）だとすると次の操作で

3/2・n + 1

となり、もとの 2n+1 より小さい数になる。よって n は奇数。

(*)⇔

2n+1 → 6n+4 → 3n+2 → 9n+7(偶数) → (9n+7)/2 →　…

ここで n は奇数なので n = 2m+1 とおくと、

(*)⇔

4m+3 → 12m+10 → 6m+5 → 18m+16 → 9m+8 →　…

この中には、２のべき乗はもちろん、(1から2nのいずれか)×(2のべき乗) も入らないです。つまり、

(2、4、8、…、16、32)

(1、2、3、…、2n-1、2n)

(2、4、6、…、2(2n-1)、2・2n)

(4、8、12、…、4(2n-1)、4・2n)

(8、16、24、…、8(2n-1)、8・2n)

…

などが入らないということです。すなわち、12m+10や18m+16などがこれらの数の中に入っていると、いずれ１に帰着してしまうのです。

続く

　コラッツの予想 (Collatz Problem)

TOP PAGE

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
0	1	7	2	5	8	16	3	19	6	14	9	9	17	17	4	12	20	20	7
21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40
7	15	15	10	23	10	111	18	18	18	106	5	26	13	13	21	21	21	34	8
41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60
109	8	29	16	16	16	104	11	24	24	24	11	11	112	112	19	32	19	32	19
61	62	63	64	65	66	67	68	69	70	71	72	73	74	75	76	77	78	79	80
19	107	107	6	27	27	27	14	14	14	102	22	115	22	14	22	22	35	35	9
81	82	83	84	85	86	87	88	89	90	91	92	93	94	95	96	97	98	99	100
22	110	110	9	9	30	30	17	30	17	92	17	17	105	105	12	118	25	25	25
101	102	103	104	105	106	107	108	109	110	111	112	113	114	115	116	117	118	119	120
25	25	87	12	38	12	100	113	113	113	69	20	12	33	33	20	20	33	33	20
121	122	123	124	125	126	127	128	129	130	131	132	133	134	135	136	137	138	139	140
95	20	46	108	108	108	46	7	121	28	28	28	28	28	41	15	90	15	41	15
141	142	143	144	145	146	147	148	149	150	151	152	153	154	155	156	157	158	159	160
15	103	103	23	116	116	116	23	23	15	15	23	36	23	85	36	36	36	54	10
161	162	163	164	165	166	167	168	169	170	171	172	173	174	175	176	177	178	179	180
98	23	23	111	111	111	67	10	49	10	124	31	31	31	80	18	31	31	31	18
181	182	183	184	185	186	187	188	189	190	191	192	193	194	195	196	197	198	199	200
18	93	93	18	44	18	44	106	106	106	44	13	119	119	119	26	26	26	119	26

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
0	1	7	2	5	8	16	3	19	6	14	9	9	17	17	4	12	20	20	7
21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40
7	15	15	10	23	10	111	18	18	18	106	5	26	13	13	21	21	21	34	8
41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60
109	8	29	16	16	16	104	11	24	24	24	11	11	112	112	19	32	19	32	19
61	62	63	64	65	66	67	68	69	70	71	72	73	74	75	76	77	78	79	80
19	107	107	6	27	27	27	14	14	14	102	22	115	22	14	22	22	35	35	9
81	82	83	84	85	86	87	88	89	90	91	92	93	94	95	96	97	98	99	100
22	110	110	9	9	30	30	17	30	17	92	17	17	105	105	12	118	25	25	25
101	102	103	104	105	106	107	108	109	110	111	112	113	114	115	116	117	118	119	120
25	25	87	12	38	12	100	113	113	113	69	20	12	33	33	20	20	33	33	20
121	122	123	124	125	126	127	128	129	130	131	132	133	134	135	136	137	138	139	140
95	20	46	108	108	108	46	7	121	28	28	28	28	28	41	15	90	15	41	15
141	142	143	144	145	146	147	148	149	150	151	152	153	154	155	156	157	158	159	160
15	103	103	23	116	116	116	23	23	15	15	23	36	23	85	36	36	36	54	10
161	162	163	164	165	166	167	168	169	170	171	172	173	174	175	176	177	178	179	180
98	23	23	111	111	111	67	10	49	10	124	31	31	31	80	18	31	31	31	18
181	182	183	184	185	186	187	188	189	190	191	192	193	194	195	196	197	198	199	200
18	93	93	18	44	18	44	106	106	106	44	13	119	119	119	26	26	26	119	26

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
0	1	7	2	5	8	16	3	19	6	14	9	9	17	17	4	12	20	20	7
21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40
7	15	15	10	23	10	111	18	18	18	106	5	26	13	13	21	21	21	34	8
41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60
109	8	29	16	16	16	104	11	24	24	24	11	11	112	112	19	32	19	32	19
61	62	63	64	65	66	67	68	69	70	71	72	73	74	75	76	77	78	79	80
19	107	107	6	27	27	27	14	14	14	102	22	115	22	14	22	22	35	35	9
81	82	83	84	85	86	87	88	89	90	91	92	93	94	95	96	97	98	99	100
22	110	110	9	9	30	30	17	30	17	92	17	17	105	105	12	118	25	25	25
101	102	103	104	105	106	107	108	109	110	111	112	113	114	115	116	117	118	119	120
25	25	87	12	38	12	100	113	113	113	69	20	12	33	33	20	20	33	33	20
121	122	123	124	125	126	127	128	129	130	131	132	133	134	135	136	137	138	139	140
95	20	46	108	108	108	46	7	121	28	28	28	28	28	41	15	90	15	41	15
141	142	143	144	145	146	147	148	149	150	151	152	153	154	155	156	157	158	159	160
15	103	103	23	116	116	116	23	23	15	15	23	36	23	85	36	36	36	54	10
161	162	163	164	165	166	167	168	169	170	171	172	173	174	175	176	177	178	179	180
98	23	23	111	111	111	67	10	49	10	124	31	31	31	80	18	31	31	31	18
181	182	183	184	185	186	187	188	189	190	191	192	193	194	195	196	197	198	199	200
18	93	93	18	44	18	44	106	106	106	44	13	119	119	119	26	26	26	119	26