콜라츠 추측 (Collatz Conjecture)

\[T(n)=\begin{cases} 3n+1 & 2\nmid n \\ n / 2 & 2\mid n \end{cases}\]

모든 자연수 $n$에 대해 위 함수를 재귀적으로 적용하면 항상 1이 된다는 추측이다.

예를 들어, 3은 3→10→5→16→8→4→2→1이다. (이후 이 수열을 전체 수열이라 부른다.)

이미 컴퓨터를 통해 $1.5 × 2^{70}$이하의 모든 자연수가 이를 만족함이 밝혀졌다.

반례가 존재한다면

만약 1로 수렴하지 않는 경우가 존재한다면 다음의 둘 중 하나일 것으로 알려져 있다.

• 무한대로 발산하는 수열이 존재한다.
• 사이클이 존재한다.

이 글에서는 사이클이 존재하는 경우에 대해 얘기하고자 한다.

요약

결론부터 얘기하자면, 사이클이 존재한다고 가정했을 때 그 최소 길이가 186,265,759,595임을 보였다. 이 경우 사이클은 홀수 72,057,431,991개와 짝수 114,208,327,604개로 구성된다. 이 값은 영문 위키피디아에 나와있으며, 해당 문서에는 더 강력한 조건 역시 실려있다.

수열 압축

함수 $T(n)$이 조건에 따라 나뉘기 때문에 좀 지저분해 보인다. 위 과정을 반복하는 것은 ‘어떤 홀수 $n$에 대해 $3n+1$에 존재하는 2를 전부 제거해 새로운 홀수를 얻는 과정’을 반복하는 것과 같다. 이를 이용해 새 함수를 정의해보자.

\[F : 2ℕ+1 \to 2ℕ+1\] \[\exists a \in ℕ, \ F(n)=\frac{3n+1}{2^a}\]

이를 이용하면 수열에서 짝수를 고려하지 않아도 된다. 예를 들어 3에 대해 위를 적용하면 3→5→1이다. (이후 이 수열을 홀수 수열이라 부른다.)

문제는 $3n+1$에 2가 인수로 몇 개 있는지 모른다는 것이다. 수열을 압축했지만 아무 소용이 없는 것이다.

하지만 그 역과정은 다르다. $3n+1$에 2를 지워 홀수를 얻는 과정을 뒤집으면, 홀수에 2를 임의로 집어 넣은 다음에 $(n-1)/3$ 하는 것과 같다. 즉, 어떤 홀수 $n$과 자연수 $a$에 대해

\[n' = \frac{2^a n - 1}{3}\]

인 홀수 $n’$은 $F(n’)=n$을 만족한다는 것이다.

$n’$이 자연수일 조건은 다음과 같다.

\[a = \begin{cases} 0 \pmod{2} & n = 1 \pmod{3} \\ 1 \pmod{2} & n = 2 \pmod{3} \end{cases}\]

$n$이 3의 배수이면 불가능하다.

이를 이용하면 $n$이 변화하는 과정을 추적하는 것에서 만드는 것으로 상황을 바꿀 수 있다.

역추적

일단 $n’$이 자연수인지 아닌지는 고려하지 말자. 그리고 역과정을 함수로 정의하자.

\[C : 2ℕ+1 \times ℕ \to ℚ\] \[C(n, a) = \frac{2^a n - 1}{3}\]

위 식이 $n$에 대한 일차식이고, 그 계수가 $a$에 대한 식임을 기억하자.

이 함수를 이용해 다음과 같이 수를 역추적하는 과정을 고려해보자.

\[\begin{gather} x_2 = C(x_1, a_1) \\ \\ x_3 = C(x_2, a_2) \\ \\ \vdots \\ \\ x_n = C(x_{n-1}, a_{n-1}) \end{gather}\]

이를 $\left\{a_n\right\}$을 타고간다,혹은 $\left\{a_n\right\}$을 거쳐간다고 표현하겠다.

이 경우 $x_n$에 대해 $T(n)$을 적용하면 $x_{n-1}$, $x_{n-2}$, $\cdots$, $x_1$을 거쳐갈 것이다.

$C$은 $n$에 대한 일차식이므로 아무리 합성해도 결국 일차식이다. 즉, $x_n$은 $x_1$에 대한 일차식으로 표현할 수 있고, 계수는 $\left\{a_n\right\}$에 대한 식이다.

정확한 식을 구하기 위해 $x_2$, $x_3$, $\cdots$, $x_n$을 차례대로 $x_1 := x$에 대한 식으로 표현해보자.

\[\begin{align} x_2 &= \frac{2^{a_1} x - 1}{3} \\ \\ x_3 &= \frac{2^{a_2} x_2 - 1}{3} \\ &= \frac{2^{a_2} \left( \displaystyle \frac{2^{a_1} x - 1}{3} \right) - 1}{3} \\ &= \frac{2^{a_1 + a_2} x - 2^{a_2} - 3}{3^2} \\ \\ x_4 &= \frac{2^{a_2} x_3 - 1}{3} \\ &= \frac{2^{a_3} \left( \displaystyle \frac{2^{a_1 + a_2} x - 2^{a_2} - 3}{3^2} \right) - 1}{3} \\ &= \frac{2^{a_1 + a_2 + a_3} x - 2^{a_2 + a_3} - 2^{a_3} \cdot 3 - 3^2}{3^3} \\ \end{align}\] \[\vdots\]

보조 수열 $\left\{S_n\right\}$을 다음과 같이 정의하자.

\[S_k = \begin{cases} \displaystyle \sum_{i=k+1}^{n}{a_i} & 0 \leq k < n \\ 0 & k = n \end{cases}\]

그러면

\[\begin{align} x_{n+1} &= \frac{2^{S_0} x - \left( 2^{S_1} + 2^{S_2} \cdot 3 + \cdots + 2^{S_n} 3^{n-1} \right)}{3^n} \\ &= \frac{ 2^{S_0} x - \displaystyle \sum_{k=1}^{n} {2^{S_k} 3^{k-1}} }{3^n} \end{align}\]

이다.

사이클

위 과정에서 수열 $x_n$이 길이 $n$인 홀수 사이클을 이룬다고 가정하자. 즉 $x_n$의 홀수 수열 $x_n$, $x_{n-1}$, $\cdots$, $x_1 (:= x)$가 사이클이라고 가정하는 것이다. 이 경우 $x_{n+1} = x$로 표현할 수 있다.

$x_{n+1}$이 $x$에 대한 일차식이므로 이것은 항상 해가 존재하며, 그 해는 계수인 $\left\{a_n\right\}$에 대한 식으로 표현된다.

\[x_{n+1} = \frac{ 2^{S_0} x - \displaystyle \sum_{k=1}^{n} {2^{S_k} 3^{k-1}} }{3^n} = x\]

에서

\[x = \frac{\displaystyle\sum_{k=1}^n {2^{S_k} 3^{k-1}}}{2^{S_0} - 3^n}\]

이다.

즉, $\left\{a_n\right\}$을 타고 가는 사이클은 유리수 범위에서 항상 유일하게 존재하며 $\left\{a_n\right\}$에 대한 식으로 표현된다. 만약 그 중에 자연수인 것이 존재하면 반례가 되는 것이다.

이제 $x$를 홀수 사이클의 최솟값이라고 가정하자. 사이클이 존재한다면 그의 모든 원소는 위와 같은 꼴로 표현될 것이기 때문에 이렇게 가정해도 무방하며, 이 경우 $a_1 \neq 1$임이 보장된다.

수열 변형

홀수 수열을 한 번 더 변형할 것이다.

다음과 같은 대소 관계를 고려해보자.

\[C(n, 1) = \frac{2n-1}{3} < n\] \[a \geq 2, \ C(n, a) \geq \frac{4n-1}{3} > n\]

$a = 1$일 때만 $C(n, a) < n$이라는 얘기이다. 따라서 $\left\{x_n\right\}$은 $\left\{a_n\right\}$이 1이면 감소하고, 아니면 증가한다.

이제 $\left\{a_n\right\}$을 1과 1이 아닌 것으로 나누어보자. $X = \left\{ a_n \right\}$에 대해

\[P = \left\{x \mid x \in X, x \neq 1\right\}\] \[N = X - P\]

로 정의하자.

나아가, $\left\{a_n\right\}$에 연속하여 나오는 1을 묶어보자. 혹은 $\left\{x_n\right\}$의 증감에 따라 묶는다고 생각할 수 있다.

예를 들어, $\left\{a_n\right\}$이 다음과 같은 경우를 고려하자.

[2, 5, 1, 1, 3, 1]

1이 연속하여 등장하는 것을 묶어주면

[2, [], 5, [1, 1], 3, [1]]

와 같다. 1이 아닌 수가 연속하여 등장하는 경우 빈 배열로 표시하였다.

이제 위를 두 수열로 다시 쪼갤 것이다. $\left\{p_n\right\}$은 1이 아닌 원소들을, $\left\{q_n\right\}$은 1이 연속으로 등장하는 횟수를 담는다. 위의 경우 $\left\{p_n\right\}$과 $\left\{q_n\right\}$은 각각 다음과 같다.

p_n = [2, 5, 3]

q_n = [0, 2, 1]

이제 이렇게 변형된 수열을 다룰 것이다.

기호 확장 및 함수 정의

먼저, $a_k = 1$이 연속하여 등장하는 부분을 묶어버리기로 했으므로, $C$를 중첩 사용할 수 있도록 표기법을 만들어보자.

\[q \geq 2, \ C^{q}(n, 1) = C(C^{q-1}(n, 1), 1)\]

이 경우 식을 다음과 같이 정리할 수 있다.

\[\begin{align} C^{q}(n, 1) &= \frac{2 \left( \frac{2 \left( \cdots \right) - 1}{3} \right) - 1}{3}\\ &= \frac{2^q n - \displaystyle\sum_{k=0}^{q-1} {2^k 3^{q-k}}}{3^q}\\ &= \frac{\displaystyle 2^q n - 3^q + 2^q}{\displaystyle 3^q}\\ &= \left( \frac{2}{3} \right)^q (n+1) - 1 \end{align}\]

이 식은 $q$에 대한 감소함수이므로, $q$를 실수 전체로 확장하겠다. 음수도 포함하는 것이다.

또한 $n$에서 $p$만큼 올라갔을 때 얼마나 내려가야 다시 $n$이 되는가를 함수로 정의할 것이다. 즉 $C^{q}(C(n, p), 1) = n$인 수 $q$의 값을 $\delta(n, p)$로 정의하겠다. 이 경우 식을 정리하면

\[C^{q}(C(n, p), 1) = \left( \frac{2}{3} \right)^q (C(n, p) + 1) - 1\]

이므로

\[\begin{align} \delta(n, p) &= q\\ &= \log_{\frac{3}{2}}{\frac{C(n, p)+1}{n+1}}\\ &= \log_{\frac{3}{2}}{\frac{2^{p-1}n +1}{n+1}} - 1 \end{align}\]

이다.

마지막으로 두 수열 $\left\{u_n\right\}$과 $\left\{d_n\right\}$을 정의할 것인데, $p$와 $q$를 거칠 때마다 등장하는 $x_n$의 값을 각각 $u$와 $d$로 정의한다고 생각하면 된다.

\[\begin{gather} d_1 = x_1\\ u_1 = C(d_1, p_1)\\ \\ d_2 = C^{q_1}(u_1, 1)\\ u_2 = C(d_2, p_2)\\ \\ \vdots\\ \\ u_k = C(d_k, p_k)\\ d_{k+1} = C^{q_k}(u_k, 1) = d_1 \end{gather}\]

보조 정리

이 장에 등장하는 $n$ (수열 $p_n$과 $q_n$의 크기)은 앞에서 등장한 $n$ (홀수 사이클의 길이)과 다르다.

\[|N| = \sum_{k=1}^n {\delta(d_k, p_k)}\]

이걸 수식으로 증명하려면 귀납적으로 증명할 수는 있지만, 말로만 설명하겠다.

앞의 모든 수열이 정해진 상황에서 사이클이 만들어지기 위한 마지막 $q_n$의 값이 무엇인지 구하려고 한다. $C$는 중첩 사용할 수 있으므로, 앞에서 $\left\{p_n\right\}$과 $\left\{q_n\right\}$으로 움직인 것을 모두 합쳐 $C^{q_n}$ 하나로 없앨 수 있다.

\[\begin{align} d_{n+1} &= C^{q_n}(u_n, 1) \\ &= C^{q_n}(C(d_n, p_n), 1) \end{align}\]

이므로 $q_n = \delta (d_n, p_n)$이면 $d_{n+1} = d_n$이다. $p_n$으로 올라간 것을 없앤 것이다.

이제 $q_{n-1}$로 내려간 것을 없애보자. $q_n$에서 $q_{n-1}$을 빼주면, 즉 $q_n = \delta (d_n, p_n) - q_{n-1}$이면 $d_{n+1} = u_n$이다.

정리하면 다음과 같이 없앨 수 있다.

• $p_k$ 되돌리기: $q_n$에 $\delta(d_k, p_k)$을 더한다
• $q_k$ 되돌리기: $q_n$에서 $q_k$를 뺀다

$p_1$, $q_1$, $p_2$, $\cdots$, $p_{n-1}$, $q_{n-1}$, $p_n$을 없애야 한다. 마지막에 $p_n$ 하나가 남는다는 점을 생각하여 정리하면

\[q_n = \sum_{k=1}^{n-1} {\left( \delta(d_k, p_k) - q_k \right)} + \delta(d_n, p_n) \\ \Rightarrow d_{n+1} = d_1\]

이다.

식이 매우 복잡해보이는데, $|N| = \displaystyle\sum_{k=1}^n q_k$이므로

\[\begin{align} |N| &= \sum_{k=1}^n q_k \\ &= \sum_{k=1}^{n-1} {q_k} + q_n \\ &= \sum_{k=1}^{n-1} {\delta(d_k, p_k)} + \delta(d_n, p_n)\\ &= \sum_{k=1}^{n} \delta(d_k, p_k) \end{align}\]

이다.

정리

$\delta(n, p)$는 $n$에 대한 단조 증가함수이다. 따라서 사이클의 최솟값 $x$에 대해 $\delta(n, p) \geq \delta(x, p)$이고, $1.5 \times 2^{70} := r$보다 작은 수는 사이클을 이루지 않음을 알고 있으므로, $\delta(n, p) > \delta(r, p) := \delta(p)$이다.

따라서

\[|N| = \sum_{k=1}^n \delta(d_k, p_k) > \sum_{p \in P} \delta(p)\]

이다.

$S_0$와 $n$의 관계

다시 원래의 $n$ (홀수 사이클의 길이)으로 돌아간다.

편의상 $S_0$를 $s$라고 하자.

$\left\{S_n\right\}$의 정의는 다음과 같다.

\[S_k = \begin{cases} \displaystyle\sum_{i=k+1}^n {a_i} & 0 \leq k < n \\ 0 & k = n \end{cases}\]

따라서

\[\begin{align} s &= \sum_{k=1}^n {a_k}\\ &= \sum_{p \in P}{p} + \sum_{q \in N}{q}\\ &= \sum_{p \in P}{p} + |N| \end{align}\]

이다.

\[\begin{align} n &= \sum_{p \in P}{1} + \sum_{q \in N}{1}\\ &= \sum_{p \in P}{1} + |N| \end{align}\]

이므로

\[\frac{s}{n} = \frac{\displaystyle \sum_{p \in P}{p} + |N|}{\displaystyle \sum_{p \in P}{1} + |N|}\]

이다.

위 식은 $\mid N \mid$에 대한 감소함수이므로

\[\frac{s}{n} < \frac{\displaystyle \sum_{p \in P}{\left( p + \delta(p) \right)}}{\displaystyle \sum_{p \in P}{\left( 1 + \delta(p) \right)}}\]

이다. 이 때

\[\frac{p + \delta(p)}{1 + \delta(p)}\]

가 $p \geq 2$에 대해 감소하므로,

\[\frac{p + \delta(p)}{1 + \delta(p)} < \frac{2 + \delta(2)}{1 + \delta(2)}\]

이다. 따라서

\[\begin{align} \frac{s}{n} &= \frac{\displaystyle \sum_{p \in P}{p + \delta(p)}}{\displaystyle \sum_{p \in P}{1 + \delta(p)}} \\ &< \frac{2 + \delta(2)}{1 + \delta(2)} \\ &= 1 + \frac{1}{\log_{\frac{3}{2}}{\frac{1.5\times 2^{71} + 1}{1.5\times 2^{70} + 1}}} \\ &= \log_2{3} + 2.38277 \cdots \times 10^{-22} \\ &:= \tau \end{align}\]

이다. $\left\{a_n\right\}$을 타고 가는 사이클이 존재할 때 그 원소에 대한 식

\[x_1=\frac{\displaystyle\sum_{k=1}^n {2^{S_k} 3^{k-1}}}{2^{S_0} - 3^n}\]

에서 분자가 양수이므로 분모도 양수여야 자연수 해가 존재한다. $2^s - 3^n > 0$에서 $s > n \log_2{3}$이다.

위에서 구한 식과 연립하면

\[\log_2{3} < \frac{s}{n} < \tau\]

이다.

해 찾기

$\log_2{3}$와 $\log_2{3} + 2.38277 \times 10^{-22}$ 사이에 존재하는 유리수($s / n$)를 찾아야 한다. $\log_2{3}$를 연분수를 이용해 근사한 것이 후보가 될 것으로 예상할 수 있다.

그러나 그 땐 이걸 몰랐다.

브루트 포스

조건식을 다음과 같이 변형하자.

\[n \log_2{3} < s < n \tau\]

위를 만족하는 자연수 $s$가 존재하는지 확인해야 하므로,

\[\lfloor n \log_2{3} \rfloor = \lfloor n \tau \rfloor\]

인지 확인하면 된다.

요약하면, 위 식이 참인 $n$에 대해 길이가 $n$인 홀수 사이클은 존재하지 않는다.

$n = 1$부터 하나하나 대입해서 확인한 결과,

\[n = 72,057,431,991\]

가 위 식을 만족하지 않는 최솟값임을 발견했다.

전체 사이클의 길이

$n$은 사이클에 존재하는 홀수의 개수이다. $s$는 짝수의 개수임을 알 수 있는데,

\[s = \sum_{k=1}^n {a_k}\]

에서 $a_k$가 2를 제거한 횟수이기 때문이다. 따라서 $n+s$는 전체 사이클의 길이이다.

$n = 72,057,431,991$의 경우 $s = 114,208,327,604$이므로 사이클의 전체 길이는 $186,265,759,595$이다.