콜라츠 추측

위키백과 ― 우리 모두의 백과사전.

콜라츠 추측 (Collatz conjecture)는 3n+1 추측, 울람 추측, 혹은 헤일스톤(우박) 수열등으로 알려져 있으며, 그것이 처음 나온 것은 1950년 정도이다. 로타르 콜라츠가 1937년에 처음 제기했다고 한다. 그 내용은 다음과 같은 조작과 관계가 있다.

  1. 자연수 n을 임의로 고른다.
  2. n이 짝수라면, 2로 나눈다; n이 홀수라면, 3을 곱하고 1을 더한다.
  3. 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... 의 루프를 돈다는 진술로 바뀐다.

[편집] 참고서적

이 문서는 수학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.