平成１４年９月１６日

＜美しい数学の話＞

第４５話　「コラッツ問題（角谷問題）」にゃんこ（二暗刻）　さんから
その１

　

コラッツの問題（数論の未解決問題）

　「正の数 ｎ をとり、これが奇数なら３倍して１を加える。偶数なら２で割る。

　　これを繰り返すとはじめにどんな ｎ を選んでも、いつかは 1 → 4 → 2 → 1 を繰り返す」

　　ｎ が 4兆まではコンピューターで確かめられている。

（富永裕久著　フェルマーの最終定理　1999-11-30 （株）ナツメ社）

Ａ-1． この問題の証明を試みるにあたり、正の整数　n0 を考える。

条件による処理後の値を nj （j：処理回数）とする。

但し、３倍して１を加えるのも、２で割るのも、共に1回の処理と数えるものとし、

ここで扱う数値を表す文字は特に断りをしない場合は全て正の整数とする。

(1) n0 = 4 のとき

n1 = n0 / 2 = 2

n2 = n1 / 2 = 1

n3 = 3n2 + 1 = 4

これで　4 , 2 , 1 , 4 , 2 , 1 が繰り返されることは確認できる

(2) n0 が偶数のとき　h を奇数とすれば

n0 =h・2^p と表せる

n0 を p 回（ 2 で割る）処理をすれば np = h （奇数）となる

np = n0/2^p = h < n0

h = 1 なら 成り立つ 。その他は奇数の場合で検討する。

(3) n0 が奇数のとき

n0 = 2m - 1 と表せる

m が 2 を約数として持つならば（偶数ならば）

k　を奇数 として

m = k・2^a , n0 = k・2^a+1 - 1　と表せる

この奇数を 3 倍して 2 で割る処理を a+1 回して n が n2a+2 になるとすれば

n1 = 3(k・2^a+1 - 1) + 1

n2 = n1 / 2

= { 3(k・2^a+1 - 1) + 1 } / 2

= k・3^1・2^a - 1

a は正の整数だから　n2 は奇数となり

n4 = (3n2 + 1) / 2

= { 3(k・3^12^a - 1) + 1} / 2

= k・3^2・2^a-1 - 1

・ ・・・・・・・・・・・・・・・・・・・・・・・・・・・

n2a+2 = (3n2a + 1) / 2

= k・3^a+1- 1 ・・・・　(1)

となり、n2a+2 は偶数となる

n2a+2 - n0 = ( k・3^a+1 - 1) - ( k・2^a+1- 1) = k ( 3^a+1 - 2^a+1 )

∴ n2a+2 - n0 = k ( 3^a+1 - 2^a+1 )

ここで a = 0 は m が奇数を意味する。

(4) 奇数 n0 を 3 倍して 2 で割る処理を 1 回して直ぐに偶数となるような n0 があるとすると

n1 = 3n0 + 1

n2 = n1/2 = (3n0 + 1)/2 が偶数だから

3n0 + 1 = 2^ak の形にならねばならない。但し　a： 2 以上の整数、k：自然数

k = (3n0 + 1)2^-a , n3 = n2/2 = (3n0 + 1)/2^2

n3 - n0 = (3n0 + 1)/4 - n0 = (3n0 + 1 - 4n0)/4 = (- n0 + 1)/4 < 0

このような n0 = (2^ak - 1)/3 は n0 より小さい n3 に帰着する。

一般的には　n0 = 4h - 3 の形では

n1 = 3n0 + 1 = 3(4h - 3) + 1 = 12h - 8

n2 = n1/2 = 6h - 4

n3 = n2/2 = 3h - 2

n3 - n0 = 3h - 2 - (4h - 3) = 1 - h ≦ 0 （等号は h = 1 でのみ成り立つ）

h = 1 では n0 = 1 で　n3 = 1 、h > 1 では n0 より小さい n3 に帰着する。

これらの n3 は h が偶数のとき偶数となり少なくとももう１回 2 で割れる。

( n0 = 5→4 , 9→7 , 13→10 , 17→13 , 21→16 , 25→19 , 29→22 ,・・・)

これに対し　n0 = 4h - 1 = h2^2 - 1 の形では

n1 = 3n0 + 1 = 3(4h - 1) + 1 = 12h - 2

n2 = n1/2 = 6h - 1 > 0 で n2 が n0 より大きい奇数となる。

(5) 奇数 n0 を 3 倍して 2 で割る処理を m(1) 回して初めて偶数となるような n0 を求める。

n1 = 3n0 + 1

n2 = n1/2 = (3n0 + 1)/2

n3 = 3n2+ 1 =3(3n0 + 1)/2 + 1 = (3^2n0 + 3^1 + 2^1)/2

n4 = n3/2 = (3^2n0 + 3^1 + 2^1)/2^2

n5 = 3n4 + 1= (3^3n0 + 3^2 + 3^12^1)/2^2 + 1 = (3^3n0 + 3^2 + 3^12^1 + 2^2)/2^2 = 3^3n0/2^2 + (3/2)^2 + (3/2)^1 + 1

n6 = n5/2 = (3^3n0 + 3^2 + 3^12^1 + 2^2)/2^3 = (3/2)^3n0 + ( (3/2)^2 + (3/2)^1 + 1)/2

n7 = 3n6 + 1 = (3^4n0 + 3^3 + 3^22^1 + 3^12^2 + 2^3)/2^3 =3(3/2)^3n0 + ((3/2)^3 + (3/2)^2 + (3/2)^1 + 1)

n8 = n7/2 = (3^4n0 + 3^3 + 3^22^1 + 3^12^2 + 2^3)/2^4 = (3/2)^4n0 + ((3/2)^3 + (3/2)^2 + (3/2)^1 + 1)/2

n9 = 3n8 + 1 = (3^5n0 +3^4 +3^32^1 + 3^22^2 + 3^12^3 + 2^4)/2^4 = 3(3/2)^4n0 + (3/2)^4 + (3/2)^3 + (3/2)^2 + (3/2)^1+1)

n10 = n9/2 = (3^5n0 + 3^4 + 3^32^1 + 3^22^2 +3^12^3 + 2^4)/2^5 = (3/2)^5n0 + (3/2)^4 + (3/2)^3 + (3/2)^2 + (3/2)^1+1)/2

・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

n2m(1) = (3^m(1)n0 + 3^m(1)-1 + 3^m(1)-22 + 3^m(1)-32^2 + ・・・ + 3^22^m(1)-3 + 3^12^m(1)-2 + 2^m(1)-1)/2^m(1)

= (3/2)^m(1)n0 + { (3/2)^m(1)-1 + (3/2)^m(1)-2 + (3/2)^m(1)-3 + ・・・ + (3/2)^2 + (3/2)^1 + 1 }2^-1

= (3/2)^m(1)n0 + 2^-1{ (3/2)^m(1) - 1 } /{ (3/2) -1 }

= (3/2)^m(1)n0 + 2^-1{ (3/2)^m(1) - 1 }/(1/2)

= (3/2)^m(1)n0 + (3/2)^m(1) - 1

= (3/2)^m(1)n0 + (3/2)^m(1) - (2/2)^m(1)

= (3^m(1)n0 + 3^m(1) - 2^m(1))/ 2^m(1)= (3/2)^m(1)(n0 + 1) - 1

n2m(1) = (3/2)^m(1)(n0 + 1) - 1 が偶数となる条件は (n0 + 1) が 2^m(1) で割り切れ且つその商が奇数である。

従って k1 を奇数として　n0 = k12^m(1) - 1 がその条件となる。

ここで m(1) = 1 のときは 前項で調べた n0 = 4h - 3 = (h2^1 - 1)2^1 - 1 形に相当する。

n2m(1) が初めて偶数になるのは　n0 = k12^m(1) - 1 で　k1 が奇数のときだから

k1 = 2h - 1 として　n0 = 2^m(1)+1h - 2^m(1) - 1 の形をとり、

n2m(1) - n0 = 3^m(1)k1 - 1 - 2^m(1)k1 + 1 = (3^m(1) - 2^m(1))k1 = (3^m(1) - 2^m(1))(2h - 1)

n2m(1) が偶数になったとき

n2m(1) = (3/2)^m(1)(n0 + 1) - 1= 3^m(1)k1 - 1

q1 を奇数 、p(1) ≧ 1 として

n2m(1) = 3^m(1)k1 - 1 = q12^p(1)　となるとき n2m(1) が初めて偶数になるとすると

このとき奇数 k1 は k1 = (q12^p(1) + 1)/3^m(1) となる。

＜例＞(n0,p(1),m(1),k1,q1)=(35,4,2,1,5),(155,1,2,39,175),(14563,15,2,3641,1)

n0

n1

n2

n3

n4

n5

n6

n7

n8

・・・

n13

・・・

n19

35

106

53

160

80

40

20

10

5

・・・

1

55

466

233

700

350

175

526

263

790

・・・

593

・・・

334

14563

43690

21845

65536

32768

16384

8192

4096

2048

・・・

256

・・・

1

m(1) = 2 , n2m(1) = n4 で太文字、斜文字は　q1

n_2m(1) を p(1) 回 2 で割れば　n_2m(1)+p(1) = q₁ なる奇数に達する。

ここで、　q₁ = n₀ となることがあるかどうかを調べる。

　　z₁ = q₁ - n₀ = (3^m(1)k₁ - 1)/2^p(1) - n₀ = {3^m(1)(n₀ + 1)/2^m(1) - 1}/2^p(1) - n₀

　　　　 = {3^m(1)(n₀ + 1)2^-p(1)-m(1) - 2^-p(1) - n₀

　　　　 = n₀(3^m(1)2^-p(1)-m(1)- 1) + 2^-p(1)(3^m(1)2^-m(1) -1)

　　 = [n₀{3^m(1)-2^p(1)+m(1)} + {3^m(1)- 2^m(1)}]/2^p(1)+m(1)

　　z₁ = 0 となるのは

　 　　　n₀ = (3^m(1) -2^m(1))/(2^p(1)+m(1)- 3^m(1)) のときであり、

　　 　　2^p(1)+m(1)- 3^m(1)　が　3^m(1)- 2^m(1) の約数となりうるのは

　 m(1) = 1 , p(1) = 1 のときで　n₀ = 1 となる。

即ち n₀ = 1 のときは　z = 0 となる。

　　 それ以外では n₀ は正の整数となり得ないので　z = 0 とはならない。　

　　 z₁ = [n₀{3^m(1)-2^p(1)+m(1)} + {3^m(1)- 2^m(1)}]/2^p(1)+m(1) において

　　　　 3^m(1) - 2^m(1) > 0 , 2^p(1)+m(1) > 0 で　

2^p(1)+m(1) - 3^m(1) は p(1) の変動により正負が入れ替わる。

　　　　 z₁ の正負の入れ替わり点は　2^p(1)+m(1)- 3 ^m(1) = 0 であるが、

　 　　 2^p(1)+m(1) - 3^m(1) ≠ 0 (第１項は偶数で、第２項は奇数) であり、

z₁ = 0 とはならない。

この q₁ が 最初の n₀ より小さくなるには z₁ < 0 とならねばならないので、

　　 n₀(3^m(1)-2^p(1)+m(1)) + 3^m(1) - 2^m(1) < 0 ∴ n₀(2^p(1)+m(1)- 3^m(1)) > (3^m(1) - 2^m(1))

　　 少なくとも 2^p(1)+m(1) > 3^m(1) が成り立たねばならない。

　　 ∴　2^p(1) > (3/2)^m(1)

　　 m(1) = 1 のときは p(1) = 1 で　n₃ が　n₀ より小さくなることは

前項で調べたとおりである。

　　上記例において

n₀ = 35 のとき　m(1) = 2, p(1) = 4, 2^p(1) > (3/2)^m(1) で　q₁ = 5 < n₀

n₀ = 155 のとき　m(1) = 2, p(1) = 1, 2^p(1) < (3/2)^m(1) で　q₁ = 175 > n₀

n₀ = 14563 のとき　m(1) = 2, p(1) = 15, 2^p(1) > (3/2)^m(1) で　q₁ = 1 < n₀

＜水の流れ：この続くは「その２」をご覧ください＜

　

　最初のページへもどる