コラッツの予想 (Collatz Problem)

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

コラッツの予想
自然数 n に対して、n が奇数なら3かけて1加える。偶数なら2で割る。以上の操作を繰り返すと、全ての自然数に関して、最終的に、1→4→2→1のループに入る。

 つまり

1→4→2→1

2→1

3→10→5→16→8→4→2→1

4→2→1 

5→16→8→4→2→1

6→3→10→5→16→8→4→2→1

7→22→11→34→17→52→26→13→40→20→10→5→…

8→4→2→1

9→28→14→7→…

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

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

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

・1→4→2→1以外のループをつくる数。

のどちらかですね。

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

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

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

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

t1 (任意の自然数)

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

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

このとき tn はいずれ(1、2)のループにはいる。

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

(-1)

(-5、-7、-10)

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

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

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

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

A1∪A2∪A3∪…∪An

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

An+1 { 2n+1、2n+1+1、2n+1+2、2n+1+3、2n+1+4、…、2n+2-3、2n+2-2、2n+2-1}

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

{ 2n+1、2n+1+2、2n+1+4、…、2n+2-4、2n+2-2}

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

{ 2n、2n+1、2n+2、…、2n+1-2、2n+1-1}

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

問題は奇数なのです。

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

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

Bn { 2n+1+1、2n+1+3、2n+1+5、2n+1+7、…、2n+2-5、2n+2-3、2n+2-1}

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

{ 3・2n+1+4、3・2n+1+10、3・2n+1+16、3・2n+1+22、…、3・2n+2-14、3・2n+2-8、3・2n+2-2}

さらに2で割ります。

{ 3・2n+2、3・2n+5、3・2n+8、3・2n+11、…、3・2n+1-7、3・2n+1-4、3・2n+1-1}

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

{ 3・2n-1+1、3・2n+5、3・2n-1+4、3・2n+11、…、3・2n+1-7、3・2n-2、3・2n+1-1}

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

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

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

( 3x + 1 )/4

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

x - ( 3x + 1 )/4 = ( x - 1)/4 = ( 2n+1 + 4m + 1 - 1)/4 > 0

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

残りは、(2n+1+4m+3)型の奇数のみです。

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

→10→5→16→8→4→2→1

→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1

11→34→17→52→26→13→40→20→10→5→16→8→4→2→1

15→46→23→70→35→106→53→160→80→40→20→10→5→16→8→4→2→1

19→58→29→88→44→22→11→…(11参照)

23→…(15参照)

27→(111回の操作で1に)

31→(106回の操作で1に)

35→(15参照)

39→118→59→178→89→268→134→67→202→101→304→152→76→38→19→(19参照)

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

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

上の例で言えば、奇数5を3倍して1足せば16になり、めでたく2のべき乗になったわけです。

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

(ある奇数)× 3 + 1 = 2k

となる(ある奇数)はどのような奇数でしょうか?

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

(2n+1+4m+3) × 3 + 1 = 2k

3・2n+1 + 12m + 10 = 2k

3・2n + 6m + 5 = 2k-1

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

3・20 + 6m + 5 = 2k-1

6m + 6 = 2k-1

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

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

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

下の表は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

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

また、例えば12と13、14と15、18と19、20と21、22と23など連続する2数で手続きの回数が同じであるケースが目につきます。

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

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) としてあらわせるとします。そうすると有限回の操作の後に、1に辿り着くか、(1→4→2→1)以外のループを形成します。

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

Sn ≦ f(n)

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

続く

<別の観点から…>

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

{1、2、3、…、2n-1、2n}

はすべて1に帰着。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 → …

この中には、2のべき乗はもちろん、(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などがこれらの数の中に入っていると、いずれ1に帰着してしまうのです。

続く

 コラッツの予想 (Collatz Problem)