수학에는 묘한 장르가 있습니다. 문제를 읽는 데 10초, 이해하는 데 1분이면 충분한데, 정작 답을 내는 데는 인류 전체가 수십 년, 어쩌면 수백 년을 써야 하는 문제들이죠. 페르마의 마지막 정리가 그랬고, 골드바흐 추측이 그렇습니다. 그리고 이 장르의 '끝판왕'이라 불러도 손색없는 문제가 바로 오늘의 주인공, 콜라츠 추측(Collatz conjecture)입니다.

이 문제는 계산기 하나만 있으면 초등학생도 직접 실험해볼 수 있습니다. 실제로 수많은 학생들이 수학 시간에 이 문제를 처음 만나고 "이게 왜 안 풀렸다는 거지?" 하며 고개를 갸웃합니다. 하지만 헝가리의 전설적 수학자 폴 에르되시(Paul Erdős)는 이 문제를 두고 이렇게 말했습니다. "수학은 아직 이런 문제를 다룰 준비가 되어 있지 않다." 오늘은 이 단순하고도 악명 높은 문제의 정체, 역사, 그리고 수학자들이 어디까지 다가갔는지를 차근차근 따라가 보겠습니다.

🎲 게임의 규칙: 단 두 줄짜리 알고리즘

먼저 규칙부터 확실히 정리합시다. 아무 양의 정수 하나를 고릅니다. 그리고 다음 규칙을 반복합니다.

수학 기호로 쓰면 이런 함수입니다.

그리고 콜라츠 추측의 내용은 다음과 같습니다.

정말 이게 전부입니다. 직접 해볼까요? 6에서 시작하면 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1. 여덟 번 만에 1에 도착합니다. 7은 조금 더 깁니다. 그림으로 그려보면 이 수열이 얼마나 요동치는지 한눈에 보입니다.

7은 22로 치솟았다가 11로 떨어지고, 다시 34, 17, 52까지 올라갔다가 결국 4 → 2 → 1로 착지합니다. 이렇게 구름 속 우박처럼 오르내리다 결국 땅으로 떨어지는 모습 때문에, 이 수열은 우박수(hailstone numbers)라는 별명으로 불립니다. 우박은 상승기류를 타고 구름 속을 여러 번 오르내리며 커지다가 마침내 땅으로 떨어지죠. 콜라츠 수열도 정확히 그런 궤적을 그립니다.

🎢 27의 롤러코스터: "작은 수"의 배신

여기까지는 귀엽습니다. 그런데 1부터 차례로 실험하다 보면 27에서 갑자기 분위기가 바뀝니다. 26까지는 대부분 몇십 단계 안에 끝나는데, 27은 무려 111단계가 걸리고 중간에 9,232까지 올라갑니다. 출발값의 340배가 넘는 높이입니다.

이 수열을 보면 묘한 공포가 듭니다. 27처럼 평범한 수가 이렇게 멀리 갔다 오는데, 훨씬 큰 수 중에는 영원히 올라가기만 하는 수가 하나쯤 숨어 있지 않을까? 아니면 1이 아닌 다른 고리에 갇혀 빙빙 도는 수가 있지 않을까? 바로 이 의심이 콜라츠 추측의 핵심입니다.

각 구간에서 가장 긴 여정을 가진 수(1에 도달하는 데 걸리는 단계 수, 즉 총 정지 시간이 가장 긴 수)를 정리하면 다음과 같습니다.

흥미로운 점은 출발값이 천만 배 커져도 단계 수는 수십 배 정도밖에 늘지 않는다는 겁니다. 이 '느린 증가'는 나중에 이야기할 확률적 직관과 정확히 맞아떨어집니다. 반대로 2의 거듭제곱은 가장 '착한' 수입니다. 2^k에서 출발하면 반으로 나누기만 k번 하면 1이니까요. 1024는 단 10단계 만에 끝납니다.

📜 이름이 여섯 개인 문제: 콜라츠 추측의 족보

이 문제는 이름이 유난히 많습니다. 콜라츠 추측, 3n+1 문제, 울람 문제, 가쿠타니 문제, 하세 알고리즘, 시러큐스 문제, 스웨이츠 추측… 이름이 많다는 건 그만큼 여러 사람이 각자의 자리에서 이 문제에 붙잡혔다는 뜻이기도 합니다.

이 분야 최고 전문가가 직접 이렇게 말할 정도라니, 문제의 난이도가 어느 정도인지 짐작이 가시죠. 그렇다면 대체 무엇이 그렇게 어려운 걸까요?

🤔 왜 증명이 안 될까? 실패할 수 있는 두 가지 시나리오

콜라츠 추측이 거짓이라면, 그 반례는 딱 두 가지 형태 중 하나여야 합니다.

콜라츠 추측을 증명한다는 건, 이 두 시나리오가 모두 불가능함을 보이는 것과 같습니다. 각각을 막는 일이 별개의 거대한 산이라는 점이 이 문제를 이중으로 어렵게 만듭니다.

📉 "평균적으로는" 줄어든다: 확률적 직관

사실 수학자들은 콜라츠 추측이 참일 것이라고 강하게 믿습니다. 그 근거 중 하나가 다음과 같은 간단한 확률적 추론입니다.

🧩 곱셈과 덧셈의 충돌

콜라츠 추측이 어려운 더 근본적인 이유는 이 규칙이 곱셈적 구조와 덧셈적 구조를 뒤섞는다는 데 있습니다. 정수의 '곱셈적 성질'(소인수분해, 몇 번 2로 나뉘는가)과 '덧셈적 성질'(1을 더하면 무엇이 되는가)은 수론에서 서로 잘 섞이지 않는 두 세계입니다. 3n이라는 곱셈 뒤에 +1이라는 덧셈이 끼어드는 순간, 3n이 가지고 있던 소인수 구조는 산산이 부서집니다. 3n+1의 소인수분해는 n의 소인수분해와 거의 아무런 관계가 없습니다.

이건 쌍둥이 소수 추측(p와 p+2가 모두 소수인 쌍이 무한히 많은가?)이나 ABC 추측처럼 수론의 최고 난제들이 공유하는 성질이기도 합니다. "곱하고 더하는" 상호작용을 통제할 범용 도구가 현재 수학에는 없습니다. 에르되시가 "수학이 준비되지 않았다"고 말한 것도 바로 이런 맥락입니다.

💻 이진수로 보면 보이는 '혼돈'

컴퓨터 과학의 시선으로 보면 더 생생합니다. 이진수에서 '2로 나누기'는 맨 오른쪽 0을 하나 지우는 것, 즉 오른쪽 시프트입니다. 반면 '3n+1'은 n을 왼쪽으로 한 칸 민 값(2n)에 n을 더하고 1을 더하는 연산입니다. 이 덧셈에서 자리올림(carry)이 연쇄적으로 발생하며 비트 패턴이 예측 불가능하게 뒤섞입니다.

def collatz_steps(n):
    steps, peak = 0, n
    while n != 1:
        if n % 2 == 0:
            n //= 2          # 짝수: 오른쪽 시프트
        else:
            n = 3 * n + 1    # 홀수: (n << 1) + n + 1
        peak = max(peak, n)
        steps += 1
    return steps, peak

print(collatz_steps(27))   # (111, 9232)

이 코드는 단 몇 줄이지만, 어떤 입력에 대해 while 반복문이 반드시 끝난다는 보장을 아무도 해줄 수 없습니다. 프로그래머 입장에서 콜라츠 추측은 "이 짧은 프로그램이 모든 입력에서 종료하는가?"라는 질문과 같습니다. 이 연결고리는 뒤에서 '결정 불가능성' 이야기로 이어집니다.

🌳 거꾸로 보면 나무가 된다: 콜라츠 그래프

콜라츠가 처음 이 문제를 그래프의 관점에서 떠올렸던 것처럼, 수열을 거꾸로 따라가 보면 아름다운 구조가 드러납니다. 1에서 출발해 "어떤 수가 다음 단계에 이 수가 되는가?"를 묻는 것이죠.

어떤 수 m에 도달하는 이전 수는 두 종류뿐입니다.

이렇게 보면 콜라츠 추측은 이렇게 다시 쓸 수 있습니다. "1을 뿌리로 하는 이 역방향 나무가, 모든 양의 정수를 빠짐없이 품는가?" 나무의 가지는 위로 끝없이 갈라지며 자라지만, 어딘가에 이 나무와 연결되지 않은 외딴 섬(다른 순환)이나 끝없이 위로만 뻗은 독립된 줄기(발산)가 있다면 추측은 무너집니다.

참고로 3의 배수에는 (m−1)/3 쪽 부모가 절대 생기지 않습니다. 3n+1은 3으로 나누면 항상 나머지가 1이니까요. 그래서 3, 6, 9, 21 같은 3의 배수는 나무에서 '2배 가지'만 계속 위로 이어지는, 더 이상 옆으로 갈라지지 않는 잎사귀 줄기 역할을 합니다. 이런 미세한 규칙성은 많이 알려져 있지만, 나무 전체의 구조를 장악하기엔 턱없이 부족합니다.

🖥️ 컴퓨터는 어디까지 확인했나

증명은 못 해도, 확인은 할 수 있습니다. 컴퓨터가 발전하면서 사람들은 점점 더 큰 수까지 콜라츠 추측을 직접 검증해왔습니다.

2⁶⁸은 대략 3해(垓), 즉 3 뒤에 0이 20개 붙은 수입니다. 이 범위 안의 모든 정수가 결국 1에 도착한다는 것이 확인된 셈입니다. 바리나는 GPU와 비트 연산 최적화를 적극 활용해 이전보다 훨씬 빠른 검증을 해냈고, 그 결과를 학술지 The Journal of Supercomputing에 발표했습니다.

게다가 검증 범위가 커질수록 생기는 부수 효과도 있습니다. 컴퓨터 검증 결과는 뒤에서 볼 "순환이 존재한다면 그 길이는 최소 얼마 이상이어야 한다"는 이론적 하한을 끌어올리는 재료로 쓰입니다. 즉, 무작정 숫자를 두드리는 작업이 아니라 이론과 맞물려 돌아가는 연구라는 뜻이죠.

🔬 수학자들의 진격: "거의 모든 수"까지는 왔다

콜라츠 추측의 연구사는 '전부'를 증명하지 못하는 대신 '거의 전부'를 증명하는 방향으로 발전해왔습니다. 여기서 '거의 모든'은 수학적으로 정확한 의미를 가집니다. 대략 말하면, 1부터 N까지의 수 중 예외가 차지하는 비율이 N이 커질수록 0에 가까워진다는 뜻입니다. (이를 자연 밀도가 1이라고 합니다.)

① 테라스(1976): 거의 모든 수는 '한 번은' 내려온다

리호 테라스는 수열이 처음으로 출발값보다 작아지는 시점, 즉 정지 시간(stopping time)에 주목했습니다. 만약 모든 수가 언젠가 자기보다 작은 수로 내려온다면, 귀납법으로 콜라츠 추측이 증명됩니다. (작은 수는 이미 1에 간다고 가정할 수 있으니까요.) 테라스는 거의 모든 정수가 유한한 정지 시간을 가진다는 것, 즉 밀도 1의 수들이 언젠가 출발값 아래로 떨어진다는 것을 증명했습니다. 같은 시기 에버렛(C. J. Everett)도 독립적으로 비슷한 결과를 얻었습니다.

이후 이 결과는 계속 강화되었습니다. 거의 모든 n의 궤도가 n^0.869 아래까지 내려간다는 결과(Allouche, 1979), n^0.7925 아래까지 내려간다는 결과(Korec, 1994) 등이 이어졌습니다. 출발값보다 '얼마나 많이' 작아지는지를 점점 더 세게 보장한 것이죠.

② 크라시코프–라가리아스(2003): 1에 가는 수가 '얼마나 많은가'

또 다른 방향은 "확실히 1에 도달하는 수가 최소 몇 개인가"를 세는 것입니다. 일리야 크라시코프와 제프리 라가리아스는 x 이하의 수 중 1에 도달하는 수의 개수가 충분히 큰 x에 대해 적어도 x^0.84개임을 증명했습니다. 이것만 보면 대단해 보이지 않을 수 있지만(전체는 x개니까), 무한히 많은 수 전체에 대해 아무것도 모르는 상태에서 이만큼의 하한을 보장하는 건 고도의 기술이 필요한 작업입니다.

③ 테렌스 타오(2019): 현재까지 가장 강력한 결과

2019년 9월, 테렌스 타오는 논문 "Almost all orbits of the Collatz map attain almost bounded values"를 arXiv에 공개했고, 이 논문은 2022년 학술지 Forum of Mathematics, Pi에 게재되었습니다. 결과를 쉬운 말로 풀면 이렇습니다.

이게 왜 대단할까요? 이전 결과들은 "N^0.7925 아래로 내려온다"처럼 N의 거듭제곱 수준까지만 보장했습니다. 타오는 이를 "원하는 만큼 1에 가까운 수준"까지 밀어붙였습니다. 콜라츠 추측이 말하는 "1까지 내려온다"에 바짝 다가선 것이죠. 그래서 그는 블로그에서 이 결과를 두고 콜라츠 추측에 거의 근접한 수준이라고 표현하면서도, 동시에 완전한 해결과는 여전히 거리가 멀다는 점을 분명히 했습니다.

타오의 증명에서 핵심은 확률론과 편미분방정식에서 쓰이는 아이디어를 가져온 것입니다. 그는 출발값을 특정 방식으로 무작위로 뽑을 때, 콜라츠 궤도가 몇 단계 지난 뒤의 분포가 마치 '열이 퍼지듯' 고르게 섞이는 성질을 정밀하게 다뤘습니다. 여기서 쓰인 밀도 개념은 일반적인 자연 밀도가 아니라 로그 밀도(logarithmic density)로, 작은 수에 더 큰 가중치를 주는 측정 방식입니다.

🔁 숨어 있는 고리를 찾아라: 순환 배제 연구

이번엔 두 번째 시나리오, 4→2→1이 아닌 다른 순환을 막는 연구입니다. 이쪽은 수론의 '디오판토스 근사' 이론이 무대에 오릅니다.

순환이 존재한다고 가정해봅시다. 그 순환에서 '×3+1' 단계가 a번, '÷2' 단계가 b번 일어난다면, 한 바퀴 돌았을 때 원래 수로 돌아와야 하므로 대략 3^a ≈ 2^b가 되어야 합니다. (+1이 미세하게 영향을 주긴 하지만요.) 즉, b/a가 log₂3 ≈ 1.58496…에 매우 가깝게 붙어야 합니다.

그런데 log₂3은 무리수이고, 분수로 얼마나 잘 근사되는지에 대해서는 정밀한 이론(연분수, 선형 형식의 로그에 대한 베이커 이론 등)이 있습니다. 이를 이용하면 "이 정도로 잘 맞는 순환은 엄청나게 길어야만 가능하다"는 결론을 끌어낼 수 있습니다.

즉, 순환이 숨어 있다면 그것은 수천만 단계가 넘는 거대한 고리여야 하고, 구조적으로도 상당히 복잡한 형태여야 합니다. 존재 가능성의 공간이 점점 좁혀지고 있지만, "완전히 없다"는 결론은 아직 아무도 내리지 못했습니다.

🌀 규칙을 살짝만 바꿔도: 3n+1이 특별한 이유

콜라츠 규칙이 얼마나 아슬아슬한 균형 위에 있는지는, 규칙을 조금만 바꿔보면 바로 드러납니다.

음의 정수로 가면: 고리가 세 개

같은 규칙을 음의 정수에 적용하면, 알려진 순환이 1→4→2→1 계열 하나가 아니라 여러 개 나타납니다.

음수에서 3n+1은 양수에서의 3n−1 규칙과 같습니다. (부호를 뒤집어 생각하면 되죠.) 그러니 '3n−1 문제'에서는 1 말고도 5, 17에서 시작하는 순환이 존재합니다. 덧셈 기호 하나만 바꿨을 뿐인데 세상이 달라지는 겁니다.

5n+1로 바꾸면: 명백한 '탈선'

홀수일 때 3 대신 5를 곱하면 상황은 더 극적입니다. 확률적 직관으로 계산하면 홀수 한 번마다 평균 배율이 5/4로, 1보다 큽니다. 즉 대부분의 수가 무한히 커질 것으로 예상됩니다. 실제로 7에서 출발한 5n+1 수열은 계산해볼수록 계속 커지는 모습을 보이며, 1로 돌아오지 않을 것으로 강하게 추정됩니다(다만 이 역시 엄밀히 증명된 것은 아닙니다). 게다가 13에서 출발하면 1이 아닌 순환에 갇힙니다.

그림 오른쪽처럼 5n+1 규칙에서는 13 → 66 → 33 → 166 → 83 → 416 → 208 → 104 → 52 → 26 → 13으로 열 개의 수가 고리를 이룹니다. 확률적 직관(평균 배율 3/4 대 5/4)이 3n+1과 5n+1의 운명을 정확히 갈라놓는다는 점에서, 3n+1이 얼마나 '절묘한 위치'에 있는 규칙인지 알 수 있습니다. 배율이 1보다 작긴 하지만 압도적으로 작진 않아서, 수열이 오르내리며 혼돈스럽게 보이는 것이죠.

🧠 콘웨이의 충격: "비슷한 문제는 원리적으로 풀 수 없다"

콜라츠 추측 이야기에서 빠질 수 없는 인물이 '라이프 게임'으로 유명한 영국 수학자 존 호턴 콘웨이(John Horton Conway)입니다. 그는 1972년, 콜라츠 함수를 일반화한 함수 족을 연구했습니다.

콜라츠 함수는 결국 "n을 2로 나눈 나머지에 따라 다른 일차식을 적용하는" 함수입니다. 콘웨이는 이를 "n을 어떤 수 m으로 나눈 나머지에 따라 각각 다른 일차식 a_in + b_i를 적용하는" 함수로 확장했습니다. 그리고 놀라운 사실을 증명합니다.

콘웨이는 이 아이디어를 발전시켜 1987년 FRACTRAN이라는 기묘한 프로그래밍 언어를 소개했습니다. 분수들의 목록만으로 이루어진 이 언어는 "현재 수에 곱해서 정수가 되는 첫 번째 분수를 곱한다"는 단 하나의 규칙만 가지는데, 놀랍게도 튜링 완전, 즉 어떤 컴퓨터 프로그램이든 흉내 낼 수 있습니다. 콘웨이는 FRACTRAN으로 소수를 차례로 만들어내는 프로그램까지 선보였죠. 콜라츠형 반복 규칙이 그 자체로 하나의 '컴퓨터'가 될 수 있다는 뜻입니다.

2007년에는 스튜어트 커츠(Stuart Kurtz)와 재닛 사이먼(Janos Simon)이 이 결과를 더 강화해, 일반화된 콜라츠 문제의 특정 형태가 계산 복잡도 계층에서 Π₂⁰-완전, 즉 정지 문제보다도 한 단계 더 어려운 수준임을 보였습니다.

🌐 다른 시선들: 2진 정수, 동역학, 그리고 확장

콜라츠 추측은 정수론에만 갇힌 문제가 아닙니다. 수학의 여러 분야가 저마다의 렌즈로 이 문제를 들여다봤습니다.

특히 마지막 성질은 꽤 직관적으로 이해할 수 있습니다. 처음 몇 단계의 짝/홀 여부는 수의 이진수 표현에서 끝자리 몇 비트에만 의존합니다. 그래서 끝자리 비트 패턴이 같은 수들은 처음 얼마간 똑같은 '오르내림 리듬'을 공유합니다. 이 리듬에서 내려가는 쪽이 압도적으로 많다는 걸 세어주면 테라스의 결과가 나옵니다. 하지만 이 방식은 언제나 "처음 k단계"만 볼 수 있다는 한계가 있습니다. 무한히 긴 미래는 여전히 안개 속입니다.

💰 현상금, 밈, 그리고 대중문화 속 콜라츠

이렇게 유명한 문제답게 현상금도 걸려 있습니다.

인터넷 문화에서도 콜라츠는 단골 소재입니다. 웹툰 xkcd에는 콜라츠 추측을 다룬 에피소드가 있는데, 친구들이 무엇을 하자고 하든 "짝수면 반으로, 홀수면 3배 더하기 1… 이걸 반복하다 보면 결국 같이 놀러 가게 된다"는 식으로 비튼 개그로 유명합니다. 또 과학 유튜브 채널 Veritasium은 2021년 이 문제를 다룬 영상을 "아무도 풀지 못한 가장 단순한 수학 문제"라는 콘셉트로 공개해 큰 조회 수를 기록했습니다. 우박수 그래프를 시각화한 '콜라츠 나무' 이미지는 굽이치는 산호나 해초처럼 보여서, 생성 예술(제너러티브 아트) 분야에서도 인기 있는 소재입니다.

사실 이렇게 수학 개념을 코드와 그래픽으로 시각화하는 작업은 그 자체로 하나의 '재능'이기도 합니다. 재능넷 같은 재능 공유 플랫폼에서 데이터 시각화나 수학 과외, 알고리즘 코딩 재능이 활발하게 거래되는 것도, 이렇게 어려운 개념을 '보이게' 만드는 능력이 그만큼 가치 있다는 방증이겠죠.

🚨 "증명했습니다!"가 쏟아지는 문제

콜라츠 추측은 문제가 쉽게 이해되는 만큼, 아마추어 증명 시도가 가장 많이 쏟아지는 문제 중 하나입니다. 인터넷 커뮤니티나 논문 사전 공개 서버에는 "콜라츠 추측을 증명했다"는 글이 꾸준히 올라옵니다. 하지만 지금까지 수학계의 검증을 통과한 완전한 증명은 단 하나도 없습니다. 흔히 반복되는 오류 패턴은 다음과 같습니다.

🗺️ 한눈에 보는 콜라츠 추측의 현주소

🌠 마치며: 두 줄짜리 규칙이 가르쳐주는 것

콜라츠 추측은 수학에서 "이해하기 쉬움"과 "풀기 쉬움"이 전혀 다른 이야기라는 사실을 가장 극적으로 보여주는 문제입니다. 짝수면 반으로, 홀수면 3배 하고 1. 이 단순한 규칙 뒤에는 곱셈과 덧셈의 충돌, 결정론과 무작위성의 경계, 계산 가능성의 한계라는 수학의 가장 깊은 질문들이 숨어 있습니다.

그래서 이 문제는 실패의 기록이면서도 동시에 진보의 기록입니다. 테라스의 밀도 논증, 디오판토스 근사를 이용한 순환 배제, 콘웨이의 결정 불가능성, 타오의 확률론적 혁신까지. 아무도 정상에 서지 못했지만, 정상을 향해 가는 길에서 수학자들은 새로운 도구를 하나씩 만들어냈습니다.

오늘 밤, 계산기나 코드 몇 줄로 직접 수 하나를 골라 우박을 띄워보세요. 그 수가 하늘 높이 치솟았다가 결국 4 → 2 → 1로 내려앉는 걸 보는 순간, 여러분은 80년 넘게 이어진 인류 최고 두뇌들의 도전에 아주 작은 발자국을 보탠 셈입니다. 그리고 어쩌면, 아직 아무도 보지 못한 그 마지막 한 걸음이 어딘가에서 누군가를 기다리고 있을지도 모릅니다. 🌧️➡️1️⃣