콜라츠 추측 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Collatz-graph-all-30-no27.svg|섬네일|100px|이 [[유향 그래프]]는 콜라츠 추측의 조작에 의해 몇 개의 자연수들이 변하는 과정을 나타낸다. 콜라츠 추측이 참이라면 이 [[그래프]]는 모두 1에 연결된다.]]

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

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

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

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

이 추측은 컴퓨터로 2<sup>68</sup><ref>Barina, D. Convergence verification of the Collatz problem. J Supercomput (2020). https://doi.org/10.1007/s11227-020-03368-x</ref>까지 모두 성립함이 확인되었다. 그러나, 아직 모든 자연수에 대한 증명은 발견되지 않고 있다. 이 문제의 해결에 500달러의 현상금을 걸었던 [[에르되시 팔]]은 "수학은 아직 이런 문제를 다룰 준비가 되어 있지 않다."는 말을 남겼다.

다음과 같은 통계적인 설명을 생각하면 이 추측은 참일 가능성이 높아 보인다. 그러나 이것이 콜라츠 추측을 증명하는 것은 아니다.
{{인용문|이 조작에 의해 만들어지는 ''홀수''들만 생각하면, 다음에 오는 홀수는 평균적으로 그 전의 수의 3/4정도의 값을 갖는다. 따라서 홀수의 수열은 점점 작아져 결국 1이 될 것이다.}}

== 콜라츠 추측의 공식 표현 ==
콜라츠 추측의 함수표현 공식
:<math>f(n)=\begin{Bmatrix}{n \over 2}, & \mbox{if }n\mbox{ is even} \\
3n+1, & \mbox{if }n\mbox{ is odd} \end{Bmatrix}</math>가 원래 정석 표현이지만 n이 홀수라고 했기에 3n+1은 짝수가 된다. 이점에서
:<math>f(n)=\begin{Bmatrix}{n \over 2}, & \mbox{if }n\mbox{ is even} \\
{3n+1 \over 2}, & \mbox{if }n\mbox{ is odd} \end{Bmatrix}</math>로 나타내기도 한다.
콜라츠 추측 공식의 [[합동 산술|합동산술(modular arithmetic)]] 표현식
:<math>f(n) =  \begin{cases} {n \over 2} & \text{if }n \equiv 0 \mod 2 \\ 3n+1 & \text{if }n \equiv 1 \mod 2  \end{cases}</math>

== 콜라츠 추측의 일반화 공식 ==
:<math>f(n)=\begin{Bmatrix}{n \over 2}, & \mbox{if }n\mbox{ is even} \\
m \cdot n+1, & \mbox{if }n\mbox{ is odd} \end{Bmatrix}</math>

== 콜라츠 추측의 일반화 공식의 응용 ==
:<math>e.g. \qquad  m = 1, \qquad </math>

:<math>f(n)=\begin{Bmatrix}{n \over 2}, & \mbox{if }n\mbox{ is even} \\
1 \cdot n+1, & \mbox{if }n\mbox{ is odd} \end{Bmatrix}</math>
:<math> m = 1</math>이면, <math>2</math>의 배수안에 존재하는 값만이 만들어지므로, <math>n</math>의 범주를 넘지 못한채로, 반복 수렴으로 <math>1</math>에 귀결된다.
:<math>e.g. \qquad  m = 2, \qquad </math>
:<math>f(n)=\begin{Bmatrix}{n \over 2}, & \mbox{if }n\mbox{ is even} \\
2 \cdot n +1, & \mbox{if }n\mbox{ is odd} \end{Bmatrix}</math>
:<math> m = 2</math>이면, 홀수<math>n</math>에 <math>2</math>가 곱해진 수는 짝수이므로 짝수에 <math>1</math>을 더하면 계속해서 무한히 증가된 값의 홀수<math>n</math>으로 만들게 된다. 그리고 콜라츠 추측의 단계 진행은 작동하지 않는다.
:<math>f(n)=\begin{Bmatrix}{n -1}, & \mbox{if }n\mbox{ is even} \\
 n-1, & \mbox{if }n\mbox{ is odd} \end{Bmatrix}</math>
:모든 자연수가 짝수에서도 <math>-1</math> 그리고 홀수에서도 <math>-1</math>을 반복한다면, 반복 수렴으로 <math>1</math>에 귀결된다.

== 콜라츠

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

:<math>16 \gets
\begin{cases}
5
 \\
32
\end{cases}</math>
:<math>16 </math>은 콜라츠 유향 그래프에서 최초의 분기점이다.
만약 콜라츠 추측이 성립한다면, 이것은 동시에 <math>8, 4, 2, 1 </math>을 제외한 모든 자연수가 <math>1</math>과 연결되기 위한 마지막 분기점이다.


:<math>1822 \gets
\begin{cases}
607
 \\
3644
\end{cases}</math>
:<math>10 \gets
\begin{cases}
3
 \\
20
\end{cases}</math>

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

== 콜라츠 그래프 분기점 수열 ==
콜라츠 그래프의 분기점 짝수 <math>{n}</math>은
:<math> 3 \cdot (n\cdot2-1) +1     \;\; , \;\; n=> 1</math>에서
규칙적으로 출현한다.

최초 출현 수열은 다음과 같다.
:<math> 4,10,16,22,28,34,40,46,52,58,64,70,76,82,88,94,100,106,112,118,124,130, \cdots</math>

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

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

== 같이 보기 ==
* [[모듈러 산술]]
== 참고 문헌 ==
* {{저널 인용|이름=Jeff|성=Lagarias|제목=The 3''x''+1 problem and its generalizations|저널=American Mathematical Monthly|권=92|날짜=1985|쪽= 3–23|url=http://www.cecm.sfu.ca/organics/papers/lagarias/|언어=en}}
* [http://mathworld.wolfram.com/CollatzProblem.html 매스월드]

== 각주 ==
{{각주}}

== 외부 링크 ==
* [[w:Distributed computing|Distributed computing]] ([[BOINC]]) [http://boinc.thesonntags.com/collatz/ project] {{웹아카이브|url=https://web.archive.org/web/20171204131813/http://boinc.thesonntags.com/collatz/}} 콜라츠 추측에 대한 분산 컴퓨팅 프로젝트

[[분류:추측]]
[[분류:수론]]
[[분류:정수열]]
[[분류:수론의 미해결 문제]]