양의 정수 하나를 고른 뒤 짝수면 2로 나누고 홀수면 3을 곱해 1을 더합니다. 나온 수에 같은 규칙을 계속 적용했을 때 언제나 1에 도착할까요? 이것이 콜라츠 추측(Collatz conjecture), 또는 3n+1 문제입니다. 규칙은 초등 산술만으로 설명되지만 모든 양의 정수에 대해 참이라는 증명도, 반례도 아직 알려지지 않았습니다. 몇 조 개의 사례를 컴퓨터로 확인하는 일과 무한히 많은 자연수를 증명하는 일은 논리적으로 다릅니다.
콜라츠 함수의 정확한 정의
양의 정수 n에 대한 함수 T를 T(n)=n/2(짝수), T(n)=3n+1(홀수)로 정의합니다. T를 반복 적용해 n,T(n),T²(n),…을 나열한 것이 n의 궤도입니다. 홀수에 3n+1을 적용하면 결과는 항상 짝수이므로 다음 단계에서는 적어도 한 번 2로 나눌 수 있습니다.
T(n) = n/2 (n이 짝수), 3n+1 (n이 홀수)
n=6이면 6→3→10→5→16→8→4→2→1이 됩니다. 1 이후에도 규칙을 계속 적용하면 1→4→2→1이라는 주기에 들어갑니다. 따라서 추측의 ‘1로 수렴한다’는 표현은 실수 수열의 극한이 1이라는 뜻이 아니라, 유한한 반복 뒤 1에 도달해 알려진 1-4-2 순환에 들어간다는 뜻입니다.
27은 작게 시작해 크게 올라갑니다
27의 궤도는 27→82→41→124→62→31→94→47처럼 시작합니다. 이 수열은 1에 도달하기 전 9,232까지 올라가며, 111번의 단계를 거칩니다. 시작값보다 계속 작아질 것이라는 단순한 귀납 가정이 통하지 않는 대표 사례입니다. 작은 입력도 오랫동안 상승과 하강을 되풀이할 수 있습니다.
| 시작값 | 1까지의 단계 수 | 도중의 특징 |
|---|---|---|
| 6 | 8 | 10과 16을 거쳐 감소 |
| 11 | 14 | 최댓값 52 |
| 27 | 111 | 최댓값 9,232 |
| 97 | 118 | 최댓값 9,232 |
정지 시간과 총 정지 시간
문헌에서는 서로 다른 두 시간을 구분합니다. 정지 시간은 궤도가 처음으로 시작값 n보다 작은 수에 도달할 때까지의 단계 수입니다. 총 정지 시간은 처음으로 1에 도달할 때까지의 단계 수입니다. 정의에 따라 홀수 단계 뒤에 이어지는 2의 나눗셈들을 한 단계로 묶는 가속 함수도 쓰이므로, 단계 수를 비교할 때 어떤 규칙을 사용했는지 확인해야 합니다.
홀수 단계만 모은 가속 콜라츠 함수
홀수 n에 3n+1을 적용한 뒤 결과에 포함된 2의 인수를 모두 나누면 다음 홀수로 바로 이동할 수 있습니다. 2-adic valuation v₂(m)을 m을 나누는 2의 최대 거듭제곱 지수라고 하면 홀수 전용 함수는 U(n)=(3n+1)/2^{v₂(3n+1)}입니다. 예를 들어 n=7이면 3×7+1=22이고 2로 한 번 나눠 U(7)=11입니다. n=5이면 16을 2⁴로 나눠 U(5)=1입니다.
이 가속 표기는 짝수 단계를 압축하지만 원래 문제를 다른 문제로 바꾸지는 않습니다. 다만 ‘한 단계’를 세는 방식이 달라져 정지 시간 값은 달라집니다. 논문이나 프로그램의 기록을 비교할 때 원래 T인지 가속 U인지 밝혀야 합니다.
평균적으로 감소해 보이는 이유와 그 한계
홀수 n에서 3n+1은 대략 3배로 키우지만, 그 뒤 2로 몇 번 나뉘는지가 크기를 좌우합니다. 홀수들이 모듈러 거듭제곱에 고르게 분포한다고 보는 확률적 모형에서는 v₂(3n+1)의 평균적인 효과가 증가를 상쇄해 로그 크기가 내려가는 경향을 예측합니다. 이런 휴리스틱은 관찰된 궤도를 설명하는 데 도움을 주지만 서로 다른 단계가 독립이라는 보장이 없으므로 전체 추측의 증명이 아닙니다.
반례가 있다면 두 형태 중 하나입니다
- 어떤 시작값의 궤도가 제한 없이 커져 다시 내려오지 않는 발산 궤도
- 1→4→2→1과 다른 양의 정수 순환에 갇히는 비자명 주기
현재까지 알려진 계산 범위에서는 이런 반례가 발견되지 않았습니다. 그러나 유한 범위를 모두 검사해도 그 다음 수에서 반례가 없다는 결론은 나오지 않습니다. ‘아주 큰 범위까지 참’은 강한 계산 증거지만 ‘모든 자연수에 대해 참’이라는 전칭 명제의 증명과 같지 않습니다.
컴퓨터 검증은 어떻게 줄여서 하나
각 수를 처음부터 끝까지 따로 계산할 필요는 없습니다. 궤도가 이미 검증된 더 작은 값에 도달하면 이후도 1로 간다는 사실을 재사용할 수 있습니다. 홀수 단계만 계산하고 2의 인수를 한꺼번에 제거하며, 중간값이 정수 자료형 범위를 넘지 않도록 큰 정수 연산이나 오버플로 검사를 사용합니다. 분산 검증에서는 구간을 나누고 독립 구현으로 결과를 교차 확인합니다.
검증 프로그램에 오버플로가 생기면 큰 양수가 음수나 작은 수로 바뀌어 거짓 결론을 낼 수 있습니다. 시작값의 범위뿐 아니라 궤도 중간의 최대값도 자료형보다 작아야 합니다. 계산 기록에는 알고리즘, 범위, 정수 정밀도와 재검증 방법이 함께 필요합니다.
부분적으로 증명된 결과
콜라츠 문제에는 전체 추측보다 약한 여러 정리가 있습니다. ‘거의 모든 수’에 대해 궤도가 어떤 의미에서 시작값보다 내려간다는 밀도 결과, 특정 길이 이하의 비자명 순환이 없다는 하한, 계산 구간의 검증 등이 알려져 있습니다. 이런 결과는 가능한 반례의 형태를 제한하지만 모든 양의 정수가 1에 도달한다는 결론까지 주지는 않습니다.
2019년 테런스 타오는 로그 밀도 의미에서 거의 모든 콜라츠 궤도가 시작값에 비해 임의로 느리게 커지는 경계 아래로 내려간다는 중요한 결과를 발표했습니다. 여기서 ‘거의 모든’은 모든 자연수를 뜻하지 않고 로그 밀도로 측정한 예외 집합이 작다는 전문적인 의미입니다. 이 정리 역시 콜라츠 추측의 완전한 증명은 아닙니다.
왜 단순한 수학적 귀납법이 어려운가
n보다 작은 모든 수가 1로 간다고 가정한 뒤 n도 증명하려면 n의 궤도가 언젠가 n보다 작아진다는 사실부터 보여야 합니다. 하지만 27처럼 오랫동안 시작값보다 커지는 사례가 있고, 일반 n에 대해 반드시 아래로 내려온다는 정리가 바로 문제의 핵심입니다. 짝수 n은 n/2로 작아져 귀납 가정을 쓸 수 있지만 홀수 n은 3n+1로 커집니다.
동역학계 관점
콜라츠 함수는 정수 집합 위의 이산 동역학계입니다. 각 정수를 꼭짓점으로, n에서 T(n)으로 향하는 화살표를 그리면 모든 꼭짓점의 출차수는 1입니다. 1-4-2 순환으로 들어오는 역방향 나무가 만들어지며, 추측은 모든 양의 정수가 이 연결 성분에 속한다는 주장으로 바꿔 말할 수 있습니다.
역방향에서는 가지 수가 일정하지 않습니다
어떤 양의 정수 m으로 한 단계 만에 들어오는 수를 거꾸로 찾아보면 2m은 항상 전단계가 됩니다. T(2m)=m이기 때문입니다. 또 (m−1)/3이 양의 홀수일 때에는 이 수도 전단계입니다. 예를 들어 m=10에는 20과 3이 들어옵니다. 반면 m=8에는 16만 바로 들어옵니다. 따라서 역방향 그래프는 모든 꼭짓점에서 똑같이 갈라지는 완전한 이진트리가 아닙니다.
(m−1)/3이 정수가 되려면 m≡1 (mod 3)이어야 하고, 그 몫이 홀수라는 조건도 필요합니다. 이 합동 조건 때문에 역방향 나무에는 가지가 많은 구간과 성긴 구간이 섞입니다. 역방향으로 1에서 출발해 수를 생성하면 1에 도달하는 수는 얼마든지 만들 수 있지만, 생성되지 않는 양의 정수가 하나도 없다는 사실을 보여야 콜라츠 추측의 증명이 됩니다.
나머지 분류만으로 문제가 끝나지 않는 이유
짝수는 즉시 절반이 되므로 홀수의 나머지 종류를 나누는 접근이 자연스럽습니다. 예를 들어 홀수 n이 1 (mod 4)이면 3n+1은 4의 배수여서 두 번 이상 2로 나눌 수 있습니다. n이 3 (mod 4)이면 3n+1은 2로는 나뉘지만 4로는 나뉘지 않습니다. 이 차이는 짧은 구간의 상승과 하강을 설명합니다.
그러나 한 번의 나머지 정보는 다음 여러 단계의 나머지를 독립적으로 정하지 못합니다. 더 높은 2의 거듭제곱을 법으로 삼아 경우를 세분하면 일정 길이의 궤도는 분석할 수 있지만 경우의 수가 계속 늘어납니다. 유한한 합동류를 모두 검사했다는 사실만으로 임의 길이의 모든 궤도가 내려간다는 결론은 나오지 않습니다.
직접 계산해 볼 때 기록할 값
시작값마다 총 정지 시간만 저장하면 궤도의 중요한 차이를 놓칠 수 있습니다. 1에 도달할 때까지의 최대값, 시작값 아래로 처음 내려가는 시점, 홀수 단계 수와 2로 나눈 횟수를 함께 기록하면 성장 양상을 비교하기 쉽습니다. 같은 최대값이나 같은 꼬리 궤도로 합류하는 서로 다른 시작값도 찾을 수 있습니다.
계산을 멈추는 조건도 분명해야 합니다. 1을 처음 만났을 때 멈추면 총 정지 시간을 얻고, 1 이후까지 실행하면 4→2→1이 끝없이 반복됩니다. 방문 집합을 저장해 다른 주기를 찾는 프로그램은 메모리를 많이 쓸 수 있으므로, 검증 목표가 단순 도달 여부인지 순환 탐지인지에 따라 알고리즘이 달라집니다.
콜라츠 추측 핵심 정리
콜라츠 추측은 짝수면 n/2, 홀수면 3n+1을 반복할 때 모든 양의 정수가 결국 1에 도달한다는 주장입니다. 많은 수가 빠르게 내려가지만 27처럼 크게 상승한 뒤 돌아오는 궤도도 있습니다. 정지 시간, 총 정지 시간, 가속 함수는 서로 다른 정의이므로 기록을 비교할 때 구분해야 합니다.
방대한 계산 검증과 확률적 직관은 추측을 지지하지만 무한 집합 전체의 증명은 아닙니다. 비자명 순환이나 발산 궤도가 없음을 모두 보여야 문제가 해결됩니다. 현재 공식적인 상태는 미해결이며, 검증된 범위를 넘어 참이라고 단정할 근거는 아직 없습니다.