問題の概要は、「任意の0でない自然数 n をとり、
|
おもしろい問題ですよね。この問題が好きで何度かやってます。
あまりしっくり来てなかったのでもう一度Schemeで書いてみました。（それでもまだなんだか・・・）
コード。ちょっと右よりなりますが気になるが・・・
(define collatz (lambda (n) (letrec ((iter (lambda (x col) (append col (cons x (cond ((= x 1) '()) ((odd? x) (iter (+ (* x 3) 1) col)) ((even? x) (iter (/ x 2) col)) (else (list #f)))))))) (iter n '()))))
実行結果。
(collatz 100) ;; = (100 50 25 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1) (collatz 1000) ;; =>(1000 500 250 125 376 188 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1)
こんなのはどうでしょう？
返信削除(define collatz-list
(lambda (n)
(do ([n n (if [even? n] (/ n 2) (+ (* n 3) 1))]
[ans '() (cons n ans)])
([= n 1] (reverse (cons 1 ans))))))
catbird
返信削除ある数が奇数なら、3を掛けて1を足す。ある数が偶数なら2で割る。計算結果が奇数なら、また3を掛けて1を足す。偶数なら、また2で割る。その計算を続けて行くと、ありとあらゆる数から始めても、最後は全て4→2→1→4→2→1の繰り返しになるのではないかと、コラッツは予想しました。
計算値が次第に小さくなって行くと、必ず最終的には4→2→1の繰り返しになってしまいます。従って、計算値が、無限に大きくなって行く様な始まりの数があれば、必ずしも4→2→1の繰り返しにはならないことが証明されます。
最初の数が奇数（Ｘ）の場合、3を掛けて1を足すと、Ｘ（奇数）×3（必ず奇数）+1＝Ｙ（必ず偶数）となります。従って、Ｙは偶数なので、次の計算は必ず割る2となります。よって、幾ら計算値をどんどん大きくしていこうとしても、Ｘ（奇数）×3+1=Ｙ（偶数）→Ｙ（偶数）÷2＝Ｚ（奇数）、Ｚ（奇数）×3+1＝Ｏ（偶数）、Ｏ（偶数）÷2＝Ｐ（奇数）と、奇数→偶数の繰り返し以上には、計算値は大きくなっては行かないことが分かります。つまり、（ある奇数×3+1）÷2の計算結果が、必ず奇数であれば、計算値は無限に大きくなって行き、必ずしも最後は4→2→1の繰り返しとはならないことが証明されます。
では、その様な始まりの奇数Ｘがあるか否か、エクセルを使って検証してみましょう。列Ａに上の行から順番に、1・3・5・7・9・11・・・・と奇数を入力してください。列Ｂに上から順に「＝（Ａ１×3+1）/2」「＝（Ａ2×3+1）/2」「＝（Ａ3×3+1）/2」・・・・と、左のＡ列の奇数を3倍して1を足し2で割る数式を入力します。列Ｃに上から順に「＝（Ｂ１×3+1）/2」「＝（Ｂ2×3+1）/2」「＝（Ｂ3×3+1）/2」・・・・Ｂ列のセルの計算値を、更に3倍して1を足し2で割る数式を入力します。同様の式をＤ列・Ｅ列・Ｆ列・・・に入力して行き、どんどん3倍して1を足し2で割る計算を行います。
この結果、全ての列の計算値が奇数となるものがあれば、計算値は無限に大きくなって行きます。そこで、各列において奇数が出現する様子を見てみましょう。Ｂ列では、上から2回に1度5・11・17・23・29・35・・と奇数が現れます。Ｃ列では、4回に1度17・35・53・71・89・107・125・・・と奇数が現れます。Ｄ列では8回に１度53・107・161・215・269・323・・・と奇数が現れます。Ｅ列では、16回に１度161・323・485・647・809・・・と奇数が現れます。Ｆ列では、32回に１度485・971・1457・1943・2429・2915・・・と奇数が現れます。Ｇ列では、64回に１度1457・2915・4373・5831・7289・・・・と奇数が現れます。以後同様に、Ｈ列では128回に１度、Ｉ列では256回に１度、Ｊ列では512回に１度奇数が現れます。
ここまでの計算で、奇数が連続するのは、512行目の1,023・1,535・2,303・3,455・5,183・7,775・11,663・17,495・26,243・39,365の1つです。3倍して1を足し2で割る計算をｎ回行えば、全ての計算値が奇数になるものは、2のｎ乗分の1に減少していきます。この事実は、簡単に証明出来るでしょう。
従って、計算を行えば行う程、計算値が奇数の連続になるものは1/2・1/4・1/8・1/16・1/32・・どんどん半分に減少していきます。しかし、無限の数の中では、2のｎ乗分の1は決して0にはなりません。3倍して1を足し2で割る計算をｎ回する場合、1から数えて2のｎ乗番目の奇数（又はその倍数番目の奇数）から始めると、ｎ回の計算結果全てが奇数となります。計算値は大きくなる一方で、4→2→1の繰り返しにはなりません。
有限の数の範囲内では、計算値がその範囲を超えるまで計算を行っていけば、奇数が連続しなくなります。しかし、無限の数の中では、常に先に2のｎ乗番目の奇数があります。それは（1+2×2のｎ乗）で表現される数値で、尽きることはありません。そのｎを∞にした数値から始めれば、無限に計算を繰り返しても4→2→1の繰り返しにはなりません。
少なくとも1組は、永遠に奇数が連続し数値が大きくなっていく組み合わせが存在します。従って、コラッツの予想は残念ながら誤っています。