本ページには広告が含まれています。
コラッツ数列とは
コラッツ数列とは任意の正の整数をnとし、nが偶数の場合はnを2で割り、奇数の場合はnに3を掛けて1を足すという処理を繰り返すことで得られる数列です。
このときどんな初期値から始めても必ず1に到達するというコラッツ予想があり、\(2^{68}\)までの初期値には成り立つことが証明されています。
この数列は1に到達して以降は1、4、2を繰り返すのみとなるので、1が数列の最後でこれ以降は省略します。
定義式は以下のとおりです。
\[ f(n)= \begin{cases} n / 2, && \text{if } n \equiv 0 \\ 3n + 1 && \text{if } n \equiv 1 \end{cases} \quad \vcenter{\hbox{$\pmod{2}$}} \]以下は初期値を58としたときのコラッツ数列を求める例です。
| ステップ | 現在の値 | 偶数/奇数 | 次の値の計算 | 次の値 |
|---|---|---|---|---|
| 1 | 58 | 偶数 | 58 ÷ 2 = 29 | 29 |
| 2 | 29 | 奇数 | 3 × 29 + 1 = 88 | 88 |
| 3 | 88 | 偶数 | 88 ÷ 2 = 44 | 44 |
| 4 | 44 | 偶数 | 44 ÷ 2 = 22 | 22 |
| 5 | 22 | 偶数 | 22 ÷ 2 = 11 | 11 |
| 6 | 11 | 奇数 | 3 × 11 + 1 = 34 | 34 |
| 7 | 34 | 偶数 | 34 ÷ 2 = 17 | 17 |
| 8 | 17 | 奇数 | 3 × 17 + 1 = 52 | 52 |
| 9 | 52 | 偶数 | 52 ÷ 2 = 26 | 26 |
| 10 | 26 | 偶数 | 26 ÷ 2 = 13 | 13 |
| 11 | 13 | 奇数 | 3 × 13 + 1 = 40 | 40 |
| 12 | 40 | 偶数 | 40 ÷ 2 = 20 | 20 |
| 13 | 20 | 偶数 | 20 ÷ 2 = 10 | 10 |
| 14 | 10 | 偶数 | 10 ÷ 2 = 5 | 5 |
| 15 | 5 | 奇数 | 3 × 5 + 1 = 16 | 16 |
| 16 | 16 | 偶数 | 16 ÷ 2 = 8 | 8 |
| 17 | 8 | 偶数 | 8 ÷ 2 = 4 | 4 |
| 18 | 4 | 偶数 | 4 ÷ 2 = 2 | 2 |
| 19 | 2 | 偶数 | 2 ÷ 2 = 1 | 1 |
初期値と次の値を並べたものがコラッツ数列となります。