정수론 · 개념 허브깊이 읽기

콜라츠 추측

Collatz Conjecture

AD 193720세기 독일 (로타 콜라츠)

개념

어떤 자연수든 짝수면 2로 나누고, 홀수면 3을 곱하고 1을 더하는 것을 반복하면 결국 1에 도달한다. 80년 동안 풀리지 않은 가장 단순한 미해결 문제.

한 호흡으로 이해하기

짝수면 2로 나누고 홀수면 3을 곱해 1을 더하는 일을 반복하면, 모든 양의 정수가 결국 1에 닿을까. 1930년대부터 알려진 이 추측은 문장은 간단하지만 일반 증명은 없다. 27은 111번 적용한 뒤 처음 1에 닿고 도중에 9232까지 오른다. 매우 큰 범위의 계산 검증과 “거의 모든 수”에 관한 부분 결과도 무한한 전체에 대한 증명은 아니다.

한눈에 보기

단계	값
0	27
1	82
2	41
3	124
4	62
5	31
6	94
7	47
8	142
9	71
10	214
11	107
12	322
13	161
14	484
15	242
16	121
17	364

27에서 시작 → 실제 전체 궤적은 111단계 만에 1. 표는 처음 18단계이며, 도중에 9232까지 치솟는다.

핵심 식

f(n) = \begin{cases} n/2 & n \text{ even} \\ 3n+1 & n \text{ odd} \end{cases}

? 모든 양의 정수가 결국 1에 도달

풀이 예제

1
Q.6에서 시작

핵심 순간

AD 1937

콜라츠가 처음 제기

독일의 로타 콜라츠가 학생 시절 발견. 너무 단순해서 수학 농담이라 부름.

AD 1972

에르되시 500 달러 상금

에르되시: "수학은 이런 종류의 문제를 풀 준비가 아직 안 되어 있다." 500달러 상금 걸음.

AD 2019

테렌스 타오 — 거의 모든 시작점

테렌스 타오가 거의 모든 시작점에 대해 콜라츠 추측이 결국 작은 수에 도달함을 증명. 부분적 진전.

오늘날의 응용

연산 시스템의 종료 증명 어려움 시연, 퍼즐·교육, 컴퓨터 프로그래밍 입문 예제, 결정 불가능 문제 후보.

MathVoyage 너머로

불러오는 중…

단계	값
0	27
1	82
2	41
3	124
4	62
5	31
6	94
7	47
8	142
9	71
10	214
11	107
12	322
13	161
14	484
15	242
16	121
17	364

단계	값
0	27
1	82
2	41
3	124
4	62
5	31
6	94
7	47
8	142
9	71
10	214
11	107
12	322
13	161
14	484
15	242
16	121
17	364

단계	값
0	27
1	82
2	41
3	124
4	62
5	31
6	94
7	47
8	142
9	71
10	214
11	107
12	322
13	161
14	484
15	242
16	121
17	364