“어떤 숫자든 마지막에는 1이 된다"는 게 정말일까? ── 콜라츠 추측을 즐겨보았다

안녕하세요! kenji입니다.

갑작스럽지만, “어떤 숫자든 최종적으로 1이 되는 규칙"이라고 들으면, 조금 신기하지 않나요?

예를 들어, 19나 87, 심지어 1000000이라도. 적당한 규칙에 따라 숫자를 조작하다 보면, 왠지 마지막에는 “1"로 수렴합니다.

그런 꿈만 같은 이야기가 바로 콜라츠 추측(Collatz Conjecture) 입니다.

애초에, 콜라츠 추측이 뭐야?

먼저 규칙을 소개하겠습니다.

시작: 임의의 양의 정수 를 선택합니다.
조작:
- 짝수라면 → 반으로 나눈다 (n → n / 2)
- 홀수라면 → 3배 하고 1을 더한다 (n → 3n + 1)

이것을 계속 반복하다 보면, 어떤 숫자든 최종적으로는 1에 도달한다 는 추측입니다.

예를 들어, 6부터 시작하면:

1
6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1

제대로 “1"이 되었습니다. 무사히 돌아왔네요!

코드로 해보자: Python으로 콜라츠

자, 이럴 때는 코드로 테스트해보는 것이 빠릅니다! Python으로 “콜라츠 수열"을 출력해 봅시다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def collatz(n):
    steps = [n]
    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3 * n + 1
        steps.append(n)
    return steps

# 예: 19부터 시작해 보기
print(collatz(19))

실행하면:

1
[19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

멋지게 1에 도달합니다. 꽤 먼 길을 돌아갔는데도 마지막에는 확실하게 골인!

참고로 27 부터 시작해도 마찬가지로 1에 도달합니다.

1
print(collatz(27))

실행하면

1
2
3
4
5
6
7
8
[27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242,
121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350,
175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167,
502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479,
1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911,
2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732,
866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35,
106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]

무려 111단계나 걸립니다!

게다가 중간에 9000 이상까지 부풀어 오르는 상황도 발생합니다. 엄청나게 길을 돌아가서 골인하는 패턴이네요.

그래서, 결국 뭐가 대단한 건데?

이 추측의 무엇이 대단하냐 하면,

증명되지 않았는데, 어떤 수로 해도 1이 되는 것 같다

는 점입니다.

어? 그럼 1조나 1경은…?

라고 생각하신 분, 예리하십니다. 실제로 컴퓨터를 사용해 “2의 68제곱” 정도까지는 확인되었고, 모두 1에 도달 하고 있습니다. 믿기지 않네요…

하지만, “전부 그렇게 된다"고 이론적으로 증명된 것은 아닙니다. 이것이 수학 세계에서 말하는 “미해결 문제"입니다.

왜 “1"이 될까? 확률론적 접근 (수학적 배경)

어떤 숫자든 최종적으로 1이 된다니 마법 같지만, 확률적인 관점 에서 보면 “음, 그렇게 될 것 같네"라는 합리적인 이유가 존재합니다.

홀수 $n$에 대해 3n + 1을 하면 답은 반드시 짝수 가 됩니다. 따라서 다음 단계에서는 반드시 2로 나누어지며, 실질적으로 $\frac{3n + 1}{2} \approx 1.5n$이 됩니다.

그리고 그 숫자가 다시 짝수가 될 확률은 $\frac{1}{2}$입니다. 만약 짝수라면, 한 번 더 2로 나누어져 $0.75n$이 되며 원래 수보다 작아집니다.

수학적으로 엄밀하지는 않지만, 홀수에서 다음 홀수로 점프할 때 “배율"의 기하 평균을 구하면 대략 $\frac{3}{4}$ 배 가 되는 것으로 알려져 있습니다 (휴리스틱 확률 모델). 즉, 평균적으로 값은 축소되는 경향이 있기 때문에, 최종적으로는 1로 빨려 들어가듯 떨어지는 것입니다.

규칙을 조금 바꾸면 어떻게 될까? (다른 추측과의 비교)

“그럼, 3배 말고 5배로 하면 어때?“라고 생각하게 되죠. 사실 이는 $5n + 1$ 문제 로 알려져 있으며, 이 경우에는 모든 수가 1로 수렴하는 것은 아닙니다.

$5n + 1$의 경우, 여러 개의 다른 루프(순환)가 존재한다는 것이 확인되었고, 무한히 커지는 수(발산)가 존재할 가능성도 지적되고 있습니다. 또한, $3n - 1$ 문제 의 경우에도 “$1 \to 2 \to 1$” 루프 외에 “$5 \to 14 \to 7 \to 20 \to 10 \to 5$“와 같은 다른 루프가 존재합니다.

콜라츠 추측의 “모든 것이 1($4 \to 2 \to 1$ 루프)로 수렴한다"는 성질이 얼마나 절묘한 균형 위에서 성립하는지 알 수 있습니다.

인류의 도달점 ①: 컴퓨터를 이용한 전수 조사의 한계

현재 전 세계의 수학자나 컴퓨터 과학 애호가들이 분산 컴퓨팅(전 세계 PC의 계산력을 결집하는 프로젝트)이나 GPU를 활용해 끊임없이 콜라츠 추측을 계산하고 있습니다.

2020년 시점으로, 무려 $2^{68}$(약 29경 5000조) 이하의 모든 초깃값에 대해 콜라츠 추측이 맞다(최종적으로 1이 된다)는 것이 컴퓨터를 통해 확인되었습니다.

하지만 수학의 세계에서는 “29경까지 확인했으니 전부 맞겠지"라고 말할 수 없습니다. 무한히 이어지는 수의 바다에서 보면 $2^{68}$조차 “첫 번째 물방울"에 불과하기 때문입니다.

인류의 도달점 ②: 결정 불가능성과 테렌스 타오의 돌파구

“왜 아무도 증명하지 못하는가?“라는 의문에 대해, 영국의 천재 수학자 존 콘웨이는 1972년에 콜라츠 추측을 조금 확장한 문제가 “결정 불가능(Turing complete)“하다 는 것을 증명했습니다. 이는 규칙에 따라서는 “1에 도달할지 여부를 판정하는 알고리즘이 원리적으로 존재하지 않는다"는, 컴퓨터 과학의 근간과 관련된 무서운 사실입니다. 콜라츠 추측 자체도 현대 수학의 틀에서는 증명 불가능한 명제일 가능성조차 있는 것입니다.

그런데 2019년, 마침내 큰 돌파구가 열립니다. 현대 최고의 천재 수학자 중 한 명인 테렌스 타오(Terence Tao) 가 “(엄밀하게 전부라고는 할 수 없지만) 거의 모든 초깃값에서 콜라츠 수열은 최종적으로 원래의 수보다 훨씬 작은 값에 도달한다“는 사실을 편미분방정식과 확률론적 기법을 구사해 증명한 것입니다.

이것은 “모두 1이 된다"는 완전한 증명은 아니지만, 인류가 콜라츠 추측의 진리에 가장 근접한 역사적 도달점 으로서 전 세계 수학계를 놀라게 했습니다.

콜라츠 씨는 누구야?

그런데 여기까지 읽고 “애초에 콜라츠가 누구야?“라는 생각이 들죠. 제대로 소개하겠습니다!

이름: 로타르 콜라츠(Lothar Collatz)
국적: 독일
생년: 1910년~1990년
직함: 수학자 (함수해석이나 정수론 분야에서 활약)

1937년에 이 추측을 제안했고, 그 후 80년 이상에 걸쳐 아무도 증명도 반증도 하지 못하고 있습니다.

참고로, 이 문제는 너무나도 단순하지만 너무나도 깊어서, 그 폴 에어디쉬(초유명 수학자)조차 이렇게 말했다고 합니다.

“수학은 아직 콜라츠를 다루기에는 미숙하다”

즉, 인류의 수학이 이 수수께끼를 아직 따라잡지 못했다는 설…

“어려운 수식"은 필요 없다

콜라츠 추측의 좋은 점은, 누구나 즐길 수 있다 는 것입니다.

종이와 펜만 있으면 할 수 있습니다. Python으로 코드를 작성하면 자동으로 테스트할 수 있습니다. 그러면서도, 최첨단 수학자들이 진심으로 도전하고 있다.

왠지 두근거리지 않나요?

부록: 한꺼번에 테스트하는 코드

여러 숫자를 한꺼번에 테스트하는 코드도 올려둘게요.

1
2
3
for n in range(1, 21):
    steps = collatz(n)
    print(f"{n}: {steps}（단계 수: {len(steps)-1}）")

이것은 “1~20"의 콜라츠 수열을 한꺼번에 출력해 줍니다.

결론: 이 세상은 역시 신기하다

이리하여, 콜라츠 추측.

엄청 단순한데
아무도 증명하지 못했고
수학계에서는 큰 문제

라는, 신기함 덩어리 같은 존재였습니다.

프로그래밍 초보자도 해볼 수 있으니, 꼭 한 번 가지고 놀아보세요~!

콜라츠 추측이란? 어떤 수든 마지막에는 1이 되는 수학의 미해결 문제를 Python으로 검증