콜라츠 추측이란?
콜라츠 추측은 '3n+1 문제'라고도 불리며, 수학에서 가장 유명한 미해결 문제 중 하나입니다. 임의의 양의 정수에서 출발해, 그 수가 짝수면 2로 나누고 홀수면 3을 곱한 뒤 1을 더합니다. 그리고 새로 나온 수에 대해 같은 과정을 반복합니다. 콜라츠 추측은 "어떤 수에서 출발하든 이 수열은 결국 1에 도달한다"고 주장합니다.
계산기 사용 방법
양의 정수를 하나 입력하면, 계산기가 내부적으로 콜라츠 수열 전체를 생성합니다. 그리고 정지 시간(1에 도달하기까지 필요한 단계 수)과 수열이 다시 줄어들기 전에 도달하는 최댓값을 함께 보여줍니다. 시작하는 수에 따라 수열이 얼마나 제각각으로 움직이는지 살펴보기에 아주 좋은 방법입니다.
공식 풀이
규칙은 경우에 따라 나뉘어 정의됩니다.
$$f(n) = \begin{cases} \dfrac{n}{2} & \text{if } n \equiv 0 \pmod{2} \\[0.6em] 3n+1 & \text{if } n \equiv 1 \pmod{2} \end{cases} \qquad n_0 = \text{Starting number}$$n이 짝수일 때 \(f(n) = n/2\), n이 홀수일 때 \(f(n) = 3n + 1\) 입니다. 값이 1에 도달하면 수열은 1, 4, 2, 1 의 순환에 빠지므로, 계산기는 1에서 단계 세기를 멈춥니다. 1에 이르기까지 f를 적용한 총 횟수가 바로 정지 시간입니다.
풀이 예시
6에서 시작해 봅시다. 6은 짝수이므로 \(6 \to 3\) (1단계). 3은 홀수이므로 \(3 \to 10\) (2단계). 이후 \(10 \to 5\) (3단계), \(5 \to 16\) (4단계), \(16 \to 8\) (5단계), \(8 \to 4\) (6단계), \(4 \to 2\) (7단계), \(2 \to 1\) (8단계). 총 8단계가 걸리며, 도달하는 최댓값은 16입니다.
자주 묻는 질문
콜라츠 추측은 증명되었나요? 아니요. 엄청나게 넓은 범위의 수에 대해 컴퓨터로 검증되었지만, 모든 경우에 대한 일반적인 증명은 아직 존재하지 않습니다.
왜 수열이 때때로 그렇게 커지나요? 홀수 단계에서는 3을 곱하기 때문에, 홀수가 연달아 나오면 절반으로 줄이는 단계가 값을 끌어내리기 전까지 수가 매우 높이 치솟을 수 있습니다.
정지 시간이란 무엇인가요? 값이 처음으로 1이 될 때까지 규칙이 적용되는 횟수를 단순히 센 것입니다.
