콜라츠 추측(Collatz conjecture)은 로타르 콜라츠(Lothar Collatz)가 1937년에 제기한 추측으로,
임의의 자연수가 다음 조작을 거쳐 항상 1이 된다는 추측이다.
1. 짝수라면 2로 나눈다.
2. 홀수라면 3을 곱하고 1을 더한다.
3. 1이면 조작을 멈추고, 1이 아니면 첫 번째 단계로 돌아간다.
예를 들어, 6에서 시작한다면, 차례로 6, 3, 10, 5, 16, 8, 4, 2, 1 이 된다.
1을 제외한 아무 자연수나 생각한 다음 그게 홀수라면 3을 곱한 다음 1을 더하고, 짝수라면 2로 나눈다. 그렇게 나온 수를 다시 저 식에 집어 넣고 이하 반복, 이걸 계속하다 보면 1이 나온다.
이 추측은 아직도 안풀려있고, 상금 1.2억엔 정도가 걸려있다고 한다.
https://mathprize.net/posts/collatz-conjecture/
A prize of 120 million JPY will be paid to those who have revealed the truth of the Collatz conjecture. The conjecture is also known as the \(3x + 1\) problem or the \(3n + 1\) problem. 120 million JPY in USD Collatz conjecture Repeatedly applying the function \(f(x)\) defined below to any positive integers will eventually result in \(1\). \[ f(x) = \left \{ \begin{array} \\ x \mathbin{/} 2 & (x \equiv 0 \pmod 2) \\ 3 x + 1 & (x \equiv 1 \pmod 2) \end{array} \right. \]
mathprize.net
존나 간단할 것같은데 왜 여태 안 풀린거임? 이보다 더 괴랄하게 생긴 것도 풀어내잖음. 좀 더 자세히 설명된 버전 읍노
일반화해서 쉽게 푸는게 어려워서 여태 안풀린듯. (정지문제를 통해 일반화한 문제는 결정 불가능하다고 증명했는데, 콜라츠 추측 역시 결정 불가능하다고 함. 꺼무위키 참조)
이해하기는 쉬운데 증명하기가 매우 어려움
직관적으로 보면 말이 되는 것 같은데... 저기서 3*n + 1 을 3*n - 1 로 바꾸면 증감을 거쳐 초기값 x 로 무한히 복귀하는 5와 17 이란 개새끼가 나온다는게 문제지. 예컨데 5의 경우 5, 14, 7, 20, 10, 5 처럼 무현루프가 나오는데 이건 돌려보기 전엔 직관적 예측이 힘들지. 게다가 1억 이하의 자연수 중에선 5, 17 둘만 그 지랄임. 그리고 콜라츠 추측에서 자연수 말고 음수 정수를 초기값으로 입력하면 또 -5, -17 둘이 그 지랄임. 그러니 콜라츠 추측에 대해서도 그런 자연수가 있을 가능성 자체를 부정 못한다는거. 직관적으론 병신이 극소수같지만 디시인사이드를 만들어보니 병신이 한둘이 아니더라 이런식ㅋㅋㅋ
12억 ㄷㄷ