홍라이프 계산기콜라츠 추측 계산기 쉽게 이해하기 — 개념과 원리
이 계산기는 아무 자연수에서 시작해 콜라츠의 3n + 1 규칙을 적용하고, 1에 이르기까지의 단계 수, 도중의 최댓값, 홀수 단계와 짝수 단계 수, 정지 시간을 알려 줍니다. 수학에서 가장 유명한 미해결 문제 가운데 하나를 직접 탐구해 볼 수 있습니다.
계산 방법
n이 짝수면: n → n ÷ 2
n이 홀수면: n → 3n + 1
값이 1이 될 때까지 반복합니다(그 뒤로는 4 → 2 → 1이 계속 반복됩니다).
- 1까지의 단계 수(전체 정지 시간) = 홀수 단계 + 짝수 단계
- 정지 시간 = 값이 처음으로 시작 수보다 작아지는 단계
- 정확한 정수 연산을 쓰므로 30자리 시작 수까지 계산할 수 있습니다.
원리
이 규칙은 줄어드는 단계(반으로 나누기)와 커지는 단계(3n + 1)를 섞습니다. n이 홀수면 3n + 1은 항상 짝수라서 커지는 단계 뒤에는 반드시 한 번 이상 반으로 나누기가 따라옵니다. 평균적으로는 나누기가 이기는데, 이것이 모든 수열이 결국 내려올 것이라고 기대하는 직관적인 이유입니다. 콜라츠 추측은 모든 자연수가 결국 1에 이른다는 주장입니다. 컴퓨터로 약 2⁷¹까지의 모든 시작 수가 확인되었지만 증명은 없습니다. 경로가 워낙 불규칙해서 바로 이웃한 수도 전혀 다르게 움직일 수 있습니다.
예제 풀이
기본값: n = 27.
- 수열은 27 → 82 → 41 → 124 → 62 → 31 → 94 → 47 → 142 → 71 → …로 시작합니다.
- 오랫동안 오르내리다가 77번째 단계에서 최댓값 9,232에 이릅니다.
- 96번째 단계에서 처음으로 27보다 작아집니다(정지 시간).
- 111단계 만에 1에 도착하며, 홀수 단계(3n + 1)가 41번, 짝수 단계(÷ 2)가 70번입니다.
결과 해석
작은 시작 수도 놀랄 만큼 긴 경로를 만들 수 있습니다. 27은 111단계가 걸리지만 26은 10단계면 끝납니다. 최댓값은 내려오기 전에 얼마나 높이 올라가는지를 보여 줍니다. 2의 거듭제곱은 모든 단계가 반으로 나누기라서 곧장 내려옵니다. 이웃한 수들을 비교해 보면 경로가 얼마나 예측하기 어려운지 실감할 수 있습니다.
흔한 실수
- 홀수에서 3을 곱하고 1을 더하는 순서를 바꾸는 경우
- 시작 수를 한 단계로 세는 경우
- 정지 시간과 전체 단계 수를 혼동하는 경우
- 컴퓨터 확인을 증명으로 여기는 경우
자주 묻는 질문
콜라츠 추측이란?
짝수는 반으로, 홀수는 3배 하고 1을 더하는 과정을 반복하면 항상 1에 이른다는 주장입니다.
27이 유명한 이유는?
작은 수인데도 111단계가 걸리고 9,232까지 올라가기 때문입니다.
콜라츠 추측은 증명되었나요?
아닙니다. 엄청난 범위의 수가 확인되었지만 증명은 없습니다.
1에 이르지 않는 수가 있으면 어떻게 되나요?
끝없이 커지거나 1이 아닌 다른 고리에 갇히는 수가 하나라도 발견되면 추측은 틀린 것이 됩니다. 지금까지는 그런 수가 발견되지 않았습니다.
출처: E. W. Weisstein, "Collatz Problem", Wolfram MathWorld