3x+1問題 - INTEGERS

$3x+1$ 問題とは

3x+1問題
与えられた自然数が偶数ならば半分にし、奇数なら $3$ 倍して $1$ 加えるという操作を考える。この操作を繰り返すと、どんな自然数であっても必ず $1$ になるであろう。

という問題で、未解決問題です。 $3n+1$ 予想、Collatz予想、角谷予想などなど様々な呼称を持ちます。

例えば、 $7$ から始めると、

$7 \to 22 \to 11 \to 34 \to 17 \to 52 \to 26 \to 13 \to 40 \to 20 \to 10 \to 5 \to 16$
$\to 8 \to 4 \to 2 \to 1$

と確かに $1$ になります。

$27$ から始めると $111$ 回、 $97$ から始めると $118$ 回の操作の後、 $1$ に到達します。

問題を解くためには

$1 \to 4 \to 2 \to 1$ 以外にループが存在しない。
発散するような数列を含まない。

ことを示す必要があります。

例えば、 $3x+1$ 問題の代わりに $3x-1$ 問題を同様に考えると、

$\displaystyle 1 \to 2 \to 1$

という自明なループの他に

$\displaystyle 17 \to 50 \to 25 \to 74 \to 37 \to 110 \to 55 \to 164 \to 82 \to 41 \to 122 \to 61$
$\to 182 \to 91 \to 272 \to 136 \to 68 \to 34 \to 17$

というループが存在します。

さて、奇数の次は絶対に偶数になるので、操作を一回分節約して $3x+1$ 作用素 $T\colon \mathbb{N} \to \mathbb{N}$ を次のように定義しましょう：

3x+1作用素 $\displaystyle T(n) := \begin{cases}\frac{n}{2} & n \equiv 0\pmod{2} \\ \frac{3n+1}{2} & n \equiv 1 \pmod{2} \end{cases}$ .

このとき、 $3x+1$ 問題は次のように言い換えられます。

3x+1予想
任意の自然数 $n$ に対して、或る $k \in \mathbb{N}$ が存在して、 $T^k(n)=1$ が成り立つ。

実は、弱 $3x+1$ 予想と呼ばれる予想があります。

定義 $3x+1$ 半群 $S$ を

$\displaystyle S:= \left. \left\langle \left\{ \frac{n}{T(n)} \right| n \in \mathbb{N} \right\} \right\rangle = \left\langle 2, \left. \left\{ \frac{2k+1}{3k+2} \right| k \geq 0 \right\} \right\rangle= \left\langle 2, \frac{1}{2}, \frac{3}{5}, \frac{5}{8}, \frac{7}{11}, \dots \right\rangle$

と定義する。ただし、乗法は $\mathbb{Q}$ における通常の乗法を考える。

弱3x+1予想 $\ \ \ S \supset \mathbb{N}$ .

3x+1 $\Longrightarrow$ 弱3x+1の証明. 任意に自然数 $n$ を取る。 $n \in S$ を示せばよい。 $3x+1$ 予想によって、或る $k \in \mathbb{N}$ が存在して、 $T^k(n)=1$ が成り立つ。まず、 $\displaystyle 2, \frac{1}{2} \in S$ なので、 $1 \in S$ であることに注意する。このとき、 $1=T(T^{k-1})(n) \in S$ および $\displaystyle \frac{T^{k-1}(n)}{T(T^{k-1}(n))} \in S$ より、 $T^{k-1}(n) \in S$ が分かる。これを繰り返せば、 $T(n) \in S$ ＆ $\displaystyle \frac{n}{T(n)} \in S$ より $n \in S$ に到達する。 Q.E.D.