콜라츠 추측
위키백과 ― 우리 모두의 백과사전.
콜라츠 추측 (Collatz conjecture)는 3n+1 추측, 울람 추측, 혹은 헤일스톤(우박) 수열등으로 알려져 있으며, 그것이 처음 나온 것은 1950년 정도이다. 로타르 콜라츠가 1937년에 처음 제기했다고 한다. 그 내용은 다음과 같은 조작과 관계가 있다.
- 자연수 n을 임의로 고른다.
- n이 짝수라면, 2로 나눈다; n이 홀수라면, 3을 곱하고 1을 더한다.
- n = 1 이면, 조작을 멈춘다.; 아니면, 2번째 단계로 돌아간다.
예를 들어, n = 6 에서 시작한다면, 수열은 6, 3, 10, 5, 16, 8, 4, 2, 1 이 된다.
콘라츠 추측은 이 과정이 어떤 값을 초기값으로 잡던간에, 언제나 멈춘다(즉 1에 도달한다.)고 말한다.
이 추측은 컴퓨터로 1.2 × 1012 의 정수까지 검사되었다. 그러나, 이 추측의 증명은 아직 발견되지 않고 있다. 폴 에르되시는 이 추측에 대해 "수학은 아직 이런 문제를 다룰 준비가 되어 있지 않다."는 말을 남겼다. 그는 이 문제의 해결에 500달러의 돈을 걸었다.
이 추측이 옳을 거라는 heuristic하고, 통계적인 설명을 펼칠 수 있다. 이 조작에 의해 만들어지는 홀수들만 생각하면, 다음에 오는 홀수는 평균적으로 그 전의 수의 3/4정도의 값을 갖는다, 따라서 결국에 수열은 바닥에 닿을 것이다.
이 문제는 다른 방식으로 기술되기도 한다. 그 때엔 종료조건 (n = 1에서 멈춤)이 없어지고, 수열은 끝없이 이어진다. 이 때에, 추측은 수열이 언제나 1, 4, 2, 1, 4, 2... 의 루프를 돈다는 진술로 바뀐다.
[편집] 참고서적
- Jeff Lagarias: The 3x+1 problem and its generalizations, American Mathematical Monthly Volume 92, 1985, pp. 3 - 23. Online at http://www.cecm.sfu.ca/organics/papers/lagarias/
- An ongoing distributed computing project verifies the Collatz conjecture for larger and larger values. Online at http://personal.computrain.nl/eric/wondrous/index.html
![]() |
이 문서는 수학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해갑시다. |