Contents

1. 개요
2. 3x + 1 문제
3. 비트로 살펴보기
   1. 비트열의 우측 끝 부분의 유형이 1000 … 01인 경우
   2. 비트열의 우측 끝 부분의 유형이 1111 … 11인 경우
4. 결론
5. References

개요

콜라츠 추측이라고도 알려져 있는 3x + 1 문제는 홀수인 정수 n을 3n + 1로, 짝수인 정수 n을 n / 2로 만드는 함수의 반복이 만들어내는 동작에 관심을 갖는다. 3x + 1 추측이 주장하는 것은, 임의의 양의 정수 n에 대해 이 함수를 반복적으로 적용하면 결국 1에 도달한다는 것이다[1].

본 글에서는 3x + 1 문제를 분석하기 위해 비트를 사용한 방법을 제시한다. 물론 아직 이 방법으로 문제를 증명을 할 수 있는지는 명확하지 않지만, 분명히 통계적 방법과 다르다.

3x + 1 문제

$3x + 1$ 문제는 다음과 같이 정의하는 함수의 반복으로 표현된다[1]:

\[\begin{equation} T(n) = \begin{cases} \frac{3n + 1}{2}& \text{if } n \equiv 1 \pmod 2 \\ \frac{n}{2}& \text{if } n \equiv 0 \pmod 2 \\ \end{cases} \end{equation}\]

비트로 살펴보기

임의의 양의 정수 $n$의 비트열 표현을 생각해보자. 여기서 우리는 이 비트열의 우측 끝 부분의 유형을 다음과 같이 세 가지로 나눌 수 있다:

\[\begin{equation} \begin{cases} 1 \underbrace{000 \dots 0}_\text{N} 0_2 & \text{(i)} \\ 1 \underbrace{000 \dots 0}_\text{N} 1_2 & \text{(ii)} \\ 1 \underbrace{111 \dots 1}_\text{N} 1_2 & \text{(iii)} \\ \end{cases} \end{equation}\]

식 $\text{(2)}$의 $\text{(i)}$의 경우에는 자명하게 $1$에 도달함을 알 수 있다. 그럼 식 $\text{(2)}$의 $\text{(ii), (iii)}$의 경우에도 $1$에 도달하는지 알아보자.

비트열의 우측 끝 부분의 유형이 1000 … 01인 경우

여기서 우리가 관심을 가지는 부분은 비트열의 우측 끝 부분의 $1000 \dots 01_2$이다. 이러한 비트열에 대해 $T(n)$을 적용하면 다음을 얻는다:

\[1 \underbrace{000 \dots 0}_\text{N} 1_2 \\ 11 \underbrace{000 \dots 0}_\text{N - 2} 10_2 \\ 11 \underbrace{000 \dots 0}_\text{N - 2} 1_2 \\ 1001 \underbrace{000 \dots 0}_\text{N - 4} 10_2 \\ 1001 \underbrace{000 \dots 0}_\text{N - 4} 1_2 \\ 11011 \underbrace{000 \dots 0}_\text{N - 6} 10_2 \\ 11011 \underbrace{000 \dots 0}_\text{N - 6} 1_2 \\\]

위 식에서 각 비트열의 우측 끝 부분의 $1000 \dots 012$에 주목하라. 그럼 $1000 \dots 01_2$의 두 개의 1 사이에 있는 0의 개수가 두 개씩 감소함을 알 수 있다. 그럼 이를 일반화해보자. 먼저 홀수인 $001_2$에 3을 곱하고 1을 더하면 $100_2$이고 이를 2로 나누면 $10_2$이다. 이때 $10_2$는 짝수이므로 2로 나누면 $1_2$이 된다. 따라서 $1 \underbrace{000 \dots 0}\text{N} 12 (N \geq 2)$이면, $T(n)$을 두 번 적용할 때마다 $N$은 2씩 감소한다. 이때, $N$이 짝수였다면 $1001_2$까지 감소할 수 있을 것이고, 홀수였다면 $10001_2$까지 감소할 수 있을 것이다. 그리고 $11_2 (=3), 101_2 (=5)$는 $1$에 도달함을 계산할 수 있다. 따라서 우측 끝 부분이 $1 \underbrace{000 \dots 0}\text{N} 1_2 (N \geq 2)$일 때, $T(n)$을 반복해서 적용하면 우측 끝 부분의 $1000 \dots 01_2$인 부분이 줄어들다가 결국 $1$이 된다.

이제 $1 \underbrace{000 \dots 0}\text{N} 1_2 (N \geq 2)$의 초기 길이인 $N + 2$의 변화를 살펴보자. 우측 끝 부분의 $1 \underbrace{000 \dots 0}\text{N} 1_2 (N \geq 2)$는 좌측 끝 비트에는 “곱하기 3”만 적용되고, 우측 끝 비트에 “곱하기 3 더하기 1”이 적용된다. 이때 “곱하기 3”은 비트열에서 최대 2비트를 증가시킨다. 이는 다음과 같이 계산할 수 있다:

\[n = \underbrace{111 \dots 1_2}_\text{N} \\ 3n = \underbrace{111 \dots 10_2}_\text{N + 1} + \underbrace{111 \dots 11_2}_\text{N} = \underbrace{1011 \dots 01_2}_\text{N + 2} \\\]

그런데 $1 \underbrace{000 \dots 0}\text{N} 1_2 (N \geq 2)$이면, $T(n)$을 두 번 적용할 때마다 $N$은 2씩 감소하므로 $1 \underbrace{000 \dots 0}\text{N} 1_2 (N \geq 2)$이면, $T(n)$을 반복적으로 적용하면 초기 길이인 $N + 2$보다 작아진다.

정리하면, 우측 끝 부분의 비트열이 $1 \underbrace{000 \dots 0}_\text{N} 1_2 (N \geq 2)$인 경우에는 $T(n)$을 반복적으로 적용함에 따라 $1000 \dots 01_2$의 두 개의 1 사이에 있는 0의 개수가 감소하면서 동시에 전체 비트열의 길이도 감소한다.

비트열의 우측 끝 부분의 유형이 1111 … 11인 경우

그럼 이제 비트열의 우측 끝 부분이 $1 \underbrace{111 \dots 1}_\text{N} 1_2$인 경우를 살펴보자. 이러한 비트열에 $T(n)$을 적용하면 다음을 얻는다:

\[1 \underbrace{111 \dots 1}_\text{N} 1_2 \\ 101 \underbrace{111 \dots 1}_\text{N - 1} 1_2 \\ 10001 \underbrace{111 \dots 1}_\text{N - 2} 1_2 \\ 110101 \underbrace{111 \dots 1}_\text{N - 3} 1_2 \\ 10100001 \underbrace{111 \dots 1}_\text{N - 4} 1_2 \\ 111100101 \underbrace{111 \dots 1}_\text{N - 5} 1_2 \\ 10110110001 \underbrace{111 \dots 1}_\text{N - 6} 1_2 \\\]

위 식에서 각 비트열의 우측 끝 부분의 $1111 \dots 112$에 주목하라. 그럼 각 비트열의 $1111 \dots 11_2$ 부분의 개수가 감소함을 알 수 있다. 그럼 이를 일반화해보자. 먼저 $1 \underbrace{111 \dots 1}\text{N} 12$에 $T(n)$을 적용하면 $101 \underbrace{111 \dots 1}\text{N - 1} 1_2$이 된다. 이때 연산이 진행됨에 따라 우측 끝 부분의 $1111 \dots 11_2$의 앞에는 항상 $0$이 존재하게 된다. 이는 $1111 \dots 11_2$의 가장 왼쪽 부분의 $1$을 연산하는 과정에서 생기는 것이므로 우측 끝 부분의 $1111 \dots 11_2$의 개수는 감소한다.

이제 $1 \underbrace{111 \dots 1}_\text{N} 1_2$의 길이인 $N + 2$를 살펴보자. $3n + 1$ 연산은 최대 2 비트를 증가시키고 그 결과는 짝수이므로 1 비트가 감소하므로 비트열의 전체 길이는 최대 1비트씩 증가한다. 이때 우측 끝 부분의 $1111 \dots 11_2$는 감소하지만 그 앞에는 항상 우측 끝 부분의 $0$이 존재한다. 즉, 우측 끝 부분의 $1111 \dots 11_2$이 $1$로 감소하면 해당 비트열은 식 $(2)$의 $\text{(ii)}$ 유형이 된다. 이때 이 유형은 비트열의 전체 길이를 감소시킨다. 이는 비트열을 증가시키는 유형이 존재하지만 해당 유형은 종료될 것이고 종료되면 증가된 비트열은 감소할 것임을 의미한다.

결론

본 글에서는 $3x + 1$ 문제에서의 임의의 수 $n$을 비트로 표현하여 문제를 분석하였고, 비트열이 증가하는 부분이 존재하지만 증가한 비트열은 감소할 것임을 보였다. 그러나 이렇게 증가한 비트열이 계속해서 감소할 것인지에 대해서는 추가해야하는 부분이 있는 것으로 보인다.

References

1. Jeff Lagarias, “The 3x + 1 problem and its generalizations,” American Mathematical Monthly, vol. 92, pp. 3 — 23, 1985.