콜라츠 추측

이 유향 그래프는 콜라츠 추측의 조작에 의해 몇 개의 자연수들이 변하는 과정을 나타낸다. 콜라츠 추측이 참이라면 이 그래프는 모두 1에 연결된다.

콜라츠 추측(Collatz conjecture)은 1937년에 처음으로 이 추측을 제기한 로타르 콜라츠의 이름을 딴 것으로 3n+1 추측, 울람 추측, 혹은 헤일스톤(우박) 수열 등 여러 이름으로 불린다. 콜라츠 추측은 임의의 자연수가 다음 조작을 거쳐 항상 1이 된다는 추측이다.

1. 짝수라면 2로 나눈다.
2. 홀수라면 3을 곱하고 1을 더한다.
3. 1이면 조작을 멈추고, 1이 아니면 첫 번째 단계로 돌아간다.

예를 들어, 6에서 시작한다면, 차례로 6, 3, 10, 5, 16, 8, 4, 2, 1 이 된다.

또, 27에서 시작하면 무려 111번을 거쳐야 1이 된다. 77번째에 이르면 9232를 정점으로 도달하다가 급격히 감소하여 34단계를 더 지나면 1이 된다.

이 추측은 컴퓨터로 2⁶⁸까지 모두 성립함이 확인되었다. 그러나, 아직 모든 자연수에 대한 증명은 발견되지 않고 있다. 이 문제의 해결에 500달러의 현상금을 걸었던 에르되시 팔은 "수학은 아직 이런 문제를 다룰 준비가 되어 있지 않다."는 말을 남겼다.

다음과 같은 통계적인 설명을 생각하면 이 추측은 참일 가능성이 높아 보인다. 그러나 이것이 콜라츠 추측을 증명하는 것은 아니다. 틀:인용문

콜라츠 추측의 공식 표현

콜라츠 추측의 함수표현 공식

$f(n)=\left\{\begin{array}{cc}\frac{n}{2},& \text{if }n\text{ is even}\\ 3n+1,& \text{if }n\text{ is odd}\end{array}\right\}$가 원래 정석 표현이지만 n이 홀수라고 했기에 3n+1은 짝수가 된다. 이점에서

$f(n)=\left\{\begin{array}{cc}\frac{n}{2},& \text{if }n\text{ is even}\\ \frac{3n+1}{2},& \text{if }n\text{ is odd}\end{array}\right\}$로 나타내기도 한다.

콜라츠 추측 공식의 합동산술(modular arithmetic) 표현식

$f(n)=\{\begin{array}{cc}\frac{n}{2}& \text{if }n\equiv 0mod2\\ 3n+1& \text{if }n\equiv 1mod2\end{array}$

콜라츠 추측의 일반화 공식

$f(n)=\left\{\begin{array}{cc}\frac{n}{2},& \text{if }n\text{ is even}\\ m\cdot n+1,& \text{if }n\text{ is odd}\end{array}\right\}$

콜라츠 추측의 일반화 공식의 응용

$e.g.m=1,$

$f(n)=\left\{\begin{array}{cc}\frac{n}{2},& \text{if }n\text{ is even}\\ 1\cdot n+1,& \text{if }n\text{ is odd}\end{array}\right\}$

$m=1$이면, $2$의 배수안에 존재하는 값만이 만들어지므로, $n$의 범주를 넘지 못한채로, 반복 수렴으로 $1$에 귀결된다.

$e.g.m=2,$

$f(n)=\left\{\begin{array}{cc}\frac{n}{2},& \text{if }n\text{ is even}\\ 2\cdot n+1,& \text{if }n\text{ is odd}\end{array}\right\}$

$m=2$이면, 홀수$n$에 $2$가 곱해진 수는 짝수이므로 짝수에 $1$을 더하면 계속해서 무한히 증가된 값의 홀수$n$으로 만들게 된다. 그리고 콜라츠 추측의 단계 진행은 작동하지 않는다.

$f(n)=\left\{\begin{array}{cc}n-1,& \text{if }n\text{ is even}\\ n-1,& \text{if }n\text{ is odd}\end{array}\right\}$

모든 자연수가 짝수에서도 $-1$ 그리고 홀수에서도 $-1$을 반복한다면, 반복 수렴으로 $1$에 귀결된다.

== 콜라츠

콜라츠 그래프의 분기

콜라츠 그래프에서 특정 짝수는 홀수에대한 $3\cdot n+1$의 수면서 동시에 짝수에 대한 $\frac{n}{2}$수가 되는 분기점이 된다.

$16\leftarrow \{\begin{array}{c}5\\ 32\end{array}$

$16$은 콜라츠 유향 그래프에서 최초의 분기점이다.

만약 콜라츠 추측이 성립한다면, 이것은 동시에 $8,4,2,1$을 제외한 모든 자연수가 $1$과 연결되기 위한 마지막 분기점이다.

$1822\leftarrow \{\begin{array}{c}607\\ 3644\end{array}$

$10\leftarrow \{\begin{array}{c}3\\ 20\end{array}$

따라서, 홀수에 대한 $3\cdot n+1$의 수 이면서 동시에 짝수에 대한 $\frac{n}{2}$수가 되는 분기점 짝수 $n$은 $n-1$에서 $\frac{n}{3}$의 수이다.

콜라츠 그래프 분기점 수열

콜라츠 그래프의 분기점 짝수 $n$은

$3\cdot (n\cdot 2-1)+1,n=>1$에서

규칙적으로 출현한다.

최초 출현 수열은 다음과 같다.

$4,10,16,22,28,34,40,46,52,58,64,70,76,82,88,94,100,106,112,118,124,130,\cdots$

이러한 콜라츠 그래프 분기점 수열은 6씩 증가하는 수열이다.

또한 십진수 30을 주기로 5개의 자리수 $4,10,16,22,28$이 순환적으로 출현한다.

같이 보기

• 모듈러 산술

참고 문헌

• 틀:저널 인용
• 매스월드

외부 링크

• Distributed computing (BOINC) project 틀:웹아카이브 콜라츠 추측에 대한 분산 컴퓨팅 프로젝트