コラッツの予想
勉強は明日からにして、今日はまたちょと趣味に走ります。
コラッツの予想(wikipedia:コラッツの問題)というものがあります。
任意の0より大きい整数 n をとり、
- n が偶数の場合、n を 2 で割る
- n が奇数の場合、n に 3 をかけて 1 を足す
文章で書くとこんな感じ(Wikipediaの記載をほぼそのまま引用)。簡単ですね。
確かめてみましょう。最初の数を 3 とすると、
3 → 10 → 5 → 16 → 8 → 4 → 2 → 1
はい、確かに最後に 1 になりました。
Rubyで整数からコラッツの数列を列挙するコードを書いてみました。
Integer#collatz
メソッドは、ブロックを指定しなければEnumerable(Enumerator)
を返すので注意。配列化するにはコメントにあるように.to_a
を、列の長さを取得するには.count
を使用してください。
てか 27 から始めると 111 手(最初の数 27 も含めて長さが 112 なので)もかかるんですね。意外と長いですね。
さて。なぜ始めから配列で返さず、Enumerable
(言い換えると「ストリーム」)で返したのかというと。
「必ず有限回で 1 に到達する」かどうか、は、まだ証明できていないからです。
つまり、「ひょっとしたら無限大に発散するかもしれない」し、「ひょっとしたらどこかで永久ループに入っちゃって、抜け出せないかもしれない」のです。それで安全性を考えて、ストリームにしているのです。
実際、「3をかけて」「1を足す」の部分(ソース中の「n*3+1 # <- *1
」の部分)を色々変えてみると、ループになったり、数がどんどん大きくなるパターンが出てきます。
例えば「n*5+1
」にすると、9.collatz{|n|p n}
が表示する数はどんどんどんどん大きくなっていき、永久に終わりません*1。
「n*3-1
」にすると、5.collatz{|n|p n}
はループします(5→14→7→20→10→5→…)*2。
本当にn*3+1
のときは必ず 1 になるのか。
どういうパターンの時に、発散やループに入らずに1に到達するのか。
所謂「数学の未解決問題」の一つです。
もし。
上のコードを適当な整数から始めて、「発散」したり、「ループ」したりしたら。
『反例発見!』
とTwitterで叫びましょう。
きっと世界中の数学者(主に整数論とか代数学者)がなんらかの反応をしますw
【追記:2012/05/05】勉強のために、コラッツの数列を列挙するコード(関数)を Python でも書いてみました。
参考までに。