こちらはコラッツ予想についてのメモしておきます。
目次
概要
コラッツ予想は、1937年にロタール・コラッツによって提唱された数学の未解決問題で非常にシンプルな計算手順に基づいています。
具体的なルールは以下の通りです。
- 任意の正の整数 n を選びます。
- n が偶数なら、n を2で割ります。
- n が奇数なら、n を3倍し、1を足します。
この手順を繰り返すと、初めに選んだ整数 n が最終的には1になります。
というのがコラッツ予想です。
この予想はシンプルながら、今のところ一般的な解は見つかっていません。
すなわち、どんな正の整数 n を選んでも、最終的には1に収束することを示す数学的な証明が存在しないのです。
コンピュータを用いて多くの数字がこのルールに従うことは実証されていますが、
どんなに多くの数字がルールに従うことを実証したとしても、任意の n 、つまりすべての正の整数 n について成り立つことを証明したことにはならないのです。
計算例
3から開始する
3から始めてコラッツ予想の手順を適用すると、以下のようになります。
- 3は奇数なので、3 * 3 + 1 = 10
- 10は偶数なので、10 / 2 = 5
- 5は奇数なので、5 * 3 + 1 = 16
- 16は偶数なので、16 / 2 = 8
- 8は偶数なので、8 / 2 = 4
- 4は偶数なので、4 / 2 = 2
- 2は偶数なので、2 / 2 = 1
これで1に到達しました。（7ターン）
27から開始する
27から始めてコラッツ予想の手順を適用すると、以下のようになります。
- 27は奇数なので、27 * 3 + 1 = 82
- 82は偶数なので、82 / 2 = 41
- 41は奇数なので、41 * 3 + 1 = 124
- 124は偶数なので、124 / 2 = 62
- 62は偶数なので、62 / 2 = 31
- 31は奇数なので、31 * 3 + 1 = 94
- 94は偶数なので、94 / 2 = 47
- 47は奇数なので、47 * 3 + 1 = 142
- 142は偶数なので、142 / 2 = 71
- 71は奇数なので、71 * 3 + 1 = 214
- 214は偶数なので、214 / 2 = 107
- 107は奇数なので、107 * 3 + 1 = 322
：
：（中略）
： - 5は奇数なので、5 * 3 + 1 = 16
- 16は偶数なので、16 / 2 = 8
- 8は偶数なので、8 / 2 = 4
- 4は偶数なので、4 / 2 = 2
- 2は偶数なので、2 / 2 = 1
これで1に到達しました。（111ターン）
こんな感じで、最初の数値が小さくてく、途中結構大きな数になったり、
回数もとんでもなく多くなったりするのが面白いです。
プログラムでトレース
コラッツ予想の過程をトレース出力する関数
- とりあえずPythonで書くとこんな感じになります。（簡単のため、エラー処理は省略しています。）
collatz.py
import sys
def collatz_trace(n):
sequence = [n]
while n != 1:
if n % 2 == 0:
n = n // 2
else:
n = 3 * n + 1
sequence.append(n)
return sequence, len(sequence) - 1
def main():
n = int(sys.argv[1])
sequence, turns = collatz_trace(n)
output = ",".join(map(str, sequence)) + f" ({turns} turns)"
print(output)
if __name__ == "__main__":
main()
実行結果
$ python .\collatz.py 27 27,82,41,124,62,31,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 (111 turns)