2008/12/17

【Scheme】SchemeでもCollatz


ということでSchemeでも今できる範囲で書いてみた。
きっとﾋﾄﾞｲのだろうけど。。
(define (collatz n)
  (display n)
  (newline)
  (if (> n 1)
    (if (even? n)
      (collatz (/ n 2))
      (collatz (+ (* n 3) 1)))))
(collatz 5)
;=> 5
;=> 16
;=> 8
;=> 4
;=> 2
;=> 1

プログラミングGauche
written by time:
labels :

1 件のコメント:

  1. 匿名2011/02/12 0:38:00

    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組は、永遠に奇数が連続し数値が大きくなっていく組み合わせが存在します。従って、コラッツの予想は残念ながら誤っています。

    返信削除

登録: コメントの投稿 (Atom)