[Algorithm] 콜라츠 추측(Collatz Conjecture) ; 우박수(Hailstone Sequence), 3N + 1 Problem

콜라츠 추측(Collatz Conjecture)

개념

Lothar Collatz (1910-1990)

• 1937년에 처음으로 이 추측을 제기한 독일의 수학자 로타르 콜라츠(1910 ~ 1990, Lorthar Collatz)의 이름을 딴 법칙
• 처음 시작은 임의의 양의 정수 `N` 에서 시작한다.
  • 만약 `N` 이 짝수이면, `N` 을 2로 나눈다.
  • 만약 `N` 이 홀수이면, `N` 에 3을 곱한 후 1을 더한다.
• 위와 같은 과정을 1이 될 때까지 반복한다.
• 예) 8 → 4 → 2 → 1, 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1
• 이러한 수들을 마치 우박이 구름 속에서 오르내리며 자라다가 지상으로 떨어지는 것과 비슷하다 하여 "우박수(Hailstone Sequence)" 또는 "3N + 1 Problem" 이라고 불리기도 한다.
• 아직까지 증명되지 않았지만, 어떤 양의 정수 `N` 이 주어졌을 때, 이와 같은 과정을 반복하다 보면 언제나 마지막에는 1로 끝나리라 추측이 된다.
• 현재까지 이 추측은 컴퓨터로 `20^{58}` 까지 모두 성립함이 확인되었다고 한다.
• 하지만, 아직 모든 자연수에 대해 성립하는지는 발견되지 않고 있다.

 

예제

3의 우박수(Hailstone Sequence) 구하기

• n의 값은 3에서 시작해서 1이 될 때까지 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 과정이 진행된다.

#include <iostream>
using namespace std;

int main() {
    int n = 3;
    
    while (n != 1) {
        cout << n << endl;
        if (n % 2 == 0) {
            n /= 2;
        }
        else {
            n = 3 * n + 1;
        }
    }
    
    return 0;
}

3
10
5
16
8
4
2