$\mathbb{N} := \{ 1, 2, \cdots\}$ を自然数全体の集合とする. 正の奇数全体の間の写像を と定義し, コラッツ写像と呼ぶ. ただし, $m$ は $3n + 1$ を割る最大の $2$ のべきとする. コラッツ写像を $k$ 回適用した値を $\rm{Col}\displaystyle^k(n)$ とする. 簡単に表すために $a_k := \rm{Col}\displaystyle^k(n)$ とおき, をコラッツ数列と呼ぶことにする. また $n$ を初期値と呼ぶことにする. 例えば, 初期値 $n = 3$ の場合, となる.とする. 任意の $n\in \mathbb{N}$ に対して $\rm{Col_{min}}\displaystyle(n) = 1$ が成り立つ, というのがコラッツ予想である.

奇数 $a_0,\ b_0\ (1 \le a_0 \lt b_0)$ を初期値とする数列を $(a_1,\ a_2,\ \cdots),\ (b_1,\ b_2,\ \cdots)$ とする. このとき, $b_0 = 4a_0 + 1$ ならば, $a_1 = b_1$ である.

証明

$a_1 = \displaystyle \frac{3a_0 + 1}{2^{m_1}}$, $b_1 = \displaystyle \frac{3b_0 + 1}{2^{n_1}}$ とする. ただし, $m_1$ は $3a_0 + 1$ を割り切る最大のべき, $n_1$ は $3b_0 + 1$ を割り切る最大のべきである. であり, $2 \nmid a_1,\ 2\nmid b_1$ であるから,となる.

$S_k := \displaystyle 2^{m_0 + m_1 + \cdots + m_k},\ m_0 := 0$ とする. このとき, 奇数の初期値 $a_0$ のコラッツ数列 $(a_1, a_2, \cdots)$ の第 $n$ 項は

証明

$n = 1$ のとき であるから成り立つ.
$n$ のとき成り立つと仮定すると となるから $n + 1$ のときも成り立つ.

$a_0 = a_1$ となるような初期値 $a_0$ は $a_0 = 1$ のみである. また, $a_0 = a_2$ となるような初期値 $a_0$ も $a_0 = 1$ のみである.

証明

• $a_0 = a_1$ の場合

であるから $a_0 = 1$ $(m_1 = 1)$ のみである.

• $a_0 = a_2$ の場合

である. $(m_1,\ m_2) = (2,\ 2)$ のとき $a_0 = 1$ である. そこで $a_0 \ge 2$ と仮定して矛盾を導く. このとき より である. また より である. さらに $\displaystyle 2^{m_1 + m_2} - 3^2 \ge 1$ より である. $(1), (2), (3)$ より $(m_1,\ m_2) = (2,\ 2)$ である. しかしこれは $a_0 \ge 2$ に矛盾する. したがって $a_0 \lt 2$ である.

$a_0 = a_3$ となるような初期値 $a_0$ は $a_0 = 1$ のみである.

証明

$a_0 = a_3$ とすると より である. $(m_1,\ m_2,\ m_3) = (2,\ 2,\ 2)$ のとき $a_0 = 1$ である. $a_0 \ge 2$ と仮定して矛盾を導く. $2^{m_1 + m_2 + m_3} - 3^3 \ge 1$ より である. $a_0 \ge 2$ より となるから である.
$m_3 = 1$ の場合 より となる.
$m_3 = 2$ の場合 より となる.
$m_3 = 3$ の場合 より となる. $(1)～(5)$ を満たす組み合わせは以下のようになり, $a_0 \in \mathbb{Z}$ に矛盾する.

初期値 $a_0 = k^2\ (k > 1,\ 2 \nmid k)$ に対して $a_1 < a_0$ である.

証明

$k = 2l + 1\ (l \ge 1)$ とすると,この分子は奇数であるから となる. したがって $a_1 \lt a_0$ である.

注記

これは次の「初期値が $4k + 1$ 型の場合の第一項」の特別な場合である.

初期値 $a_0 = 4k + 1$ に対して $a_1 < a_0$ である.

証明

であるから $a_1 \lt a_0$ である.

注記

$k$ が偶数の場合, $3k + 1$ は奇数であるから となる.

初期値 $a_0 = 4k + 3$ に対して $a_1 > a_0$ である.

証明

であり, この分子は奇数であるから $m_1 = 1$ となり, $a_1 = 6k + 5 \gt a_0$.

$a \in \mathbb{N}$ を奇数とする. このとき次は同値である:
$(1)$ $\rm{Col_{min}}(a) = 1.$
$(2)$ ある $n \in \mathbb{N}$ と自然数の組 $(l_1, l_2, \cdots, l_n)$ が存在してとなる.

証明

$(1) \implies (2)$
よりしたがう.
$(2) \implies (1)$
$a_0:= a,\ a_k:=\displaystyle \frac{3a_{k - 1} + 1}{2^{l_k}},\ T_k:= \displaystyle 2^{l_1 + \cdots l_k}$ とおくと, $(*)$ はとなるため, $(\implies)$ の式変形により $a_n = 1$ となる. 各 $l_k$ が $3a_{k - 1} + 1$ を割る最大の $2$ べきであることを示す. まず, $a_k\in \mathbb{N}\ (1 \le k \le n)$ であることを示す. そうでないと仮定する. $a_r\notin \mathbb{N}$ となるような最小の $1 \le r \le n$ をとる. このとき, と表せる. このとき となる. これを繰り返すとすべての $r\le j \le n$ に対して $a_j\notin \mathbb{N}$ となるが, これは $a_n = 1$ に矛盾する. よってすべての $1\le k \le n$ に対して $a_k \in \mathbb{N}$ である.
次に $2 \mid a_r$ なる $1 \le r \le n$ が存在すると仮定すると $a_{r + 1} = \displaystyle \frac{3a_r + 1}{2^{l_{r + 1}}}\notin \mathbb{N}$となり矛盾. よってすべての $a_k\ (1 \le k \le n)$ は奇数であるから, 各 $2^{l_k}$ は $3a_{k - 1} + 1$ を割る最大の $2$ べきである. これはコラッツ操作にほかならない.

例

• $a = 3$

コラッツ数列は $(5, 1)$ より $n = 2$, $2$ べき数列は $(1, 4)$ であるから

• $a = 5$

コラッツ数列は $(1)$ より $n = 1$, $2$ べき数列は $(4)$ より

• $a = 7$

コラッツ数列は $(11, 17, 13, 5, 1)$ より $n = 5$, $2$ べき数列は $(1, 1, 2, 3, 4)$ より

注記

とおくと, を示さなくてはならない. $\displaystyle C_1 = \left\{ \frac{2^m - 1}{3} \mid m \in \mathbb{N} \right\}$ であり, $C_1$ に含まれる自然数全体を考えると $m$ は偶数になるので $\{1, 5, 21, 85, 341,\cdots\}$ となる. このように $C_1$ では隙間が大きすぎるが, すべての $C_n$ を合わせることで $\mathbb{N}$ を覆うことができるだろうか.