콜라츠 추측

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

콜라츠 추측은 임의의 양의 정수 n에 대해, n이 짝수이면 2로 나누고, 홀수이면 3을 곱한 후 1을 더하는 연산을 반복하면, 어떤 수로 시작하든 결국 1에 도달한다는 추측이다. 이 연산을 수학적으로 표현하면, 짝수일 때는 n/2, 홀수일 때는 (3n+1)이며, 이를 반복하여 수열을 생성한다. 콜라츠 추측은 아직 증명되지 않았지만, 2⁶⁸까지의 모든 숫자에서 확인되었으며, 컴퓨터 계산, 확률론적 휴리스틱, 정지 시간 분석 등의 다양한 접근 방식이 시도되고 있다. 콜라츠 추측은 정수 전체, 유리수, 2진 정수로 확장될 수 있으며, 일반화된 형태는 계산 불가능한 문제로 증명되었다.

더 읽어볼만한 페이지

추측 - P-NP 문제
P-NP 문제는 계산 복잡도 이론에서 P와 NP 복잡도 종류의 관계에 대한 미해결 문제로, 컴퓨터 과학과 수학에 혁명적인 변화를 가져올 것으로 예상되며 암호학, 최적화, 인공지능 등 다양한 분야에 큰 영향을 미칠 수 있다.
추측 - 버치-스위너턴다이어 추측
버치-스위너턴다이어 추측은 타원 곡선의 유리점 구조와 L-함수 특성 간의 관계를 추측하는 미해결 문제로, 타원 곡선의 랭크가 L-함수의 s=1에서의 영점 차수와 같다고 주장하며, 클레이 수학 연구소의 밀레니엄 문제 중 하나이다.
수론의 미해결 문제 - 오일러-마스케로니 상수
오일러-마스케로니 상수 $\gamma$ 는 조화급수와 자연로그 함수의 차이의 극한으로 정의되는 수학 상수로, 감마 함수, 리만 제타 함수 등 다양한 수학적 개념과 관련되어 있으며 유리수인지 무리수인지 밝혀지지 않은 미해결 문제이다.
수론의 미해결 문제 - 리만 가설
리만 가설은 리만 제타 함수의 자명하지 않은 모든 영점의 실수부가 1/2이라는 추측으로, 힐베르트 문제와 클레이 수학 연구소의 밀레니엄 문제 중 하나이며 정수론과 복소해석학을 연결하는 다양한 수학적 명제들과 동치이다.
정수열 - 실베스터 수열
실베스터 수열은 각 항이 이전 항들의 곱에 1을 더한 값으로 정의되는 정수 수열로서, 재귀적으로 정의되며 이중 지수 함수적으로 증가하고, 이집트 분수 및 탐욕 알고리즘과 관련이 있으며, 역수 합은 1로 수렴한다.
정수열 - 소수 (수론)
소수는 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수이며, 무한히 많고 정수론의 기본 정리에서 중요한 역할을 하며 다양한 분야에 응용된다.

콜라츠 추측
개요
이름	콜라츠 추측
다른 이름	3n+1 문제 3x+1 문제 울람 추측 가쿠타니 문제 튜웨이츠 추측 하세 알고리즘 시라쿠사 문제
설명	모든 양의 정수에 대해, 짝수면 2로 나누고 홀수면 3을 곱한 후 1을 더하는 과정을 반복하면 결국 1에 도달한다는 추측임.
최초 제안자	로타르 콜라츠
미해결 문제 분야	수학
세부 내용
공식	f(n) = n/2 (n이 짝수일 때) f(n) = 3n+1 (n이 홀수일 때)
반례 탐색 범위	2.95e20
테렌스 타오의 연구	콜라츠 추측의 거의 모든 궤도가 거의 제한된 값에 도달한다는 것을 증명함.
추가 정보
관련 링크	MathWorld: 콜라츠 문제 Numberphile: 콜라츠 추측

2. 콜라츠 추측의 정의

콜라츠 추측은 임의의 양의 정수에 대해 특정 연산을 반복하면 결국 1에 도달한다는 내용이다. 이 추측은 아직 증명되지 않았지만, 컴퓨터 계산을 통해 2⁶⁸까지의 모든 수에 대해 성립함이 확인되었다.^[23]

만약 콜라츠 추측이 거짓이라면, 1로 수렴하지 않고 다른 순환에 빠지거나 무한히 발산하는 초기값이 존재해야 한다. 하지만 현재까지 이러한 수열은 발견되지 않았다.

2. 1. 연산 규칙

임의의 양의 정수 n에 대해, 다음과 같은 연산을 정의한다.

n이 짝수이면, n을 2로 나눈다.
n이 홀수이면, n에 3을 곱하고 1을 더한다.

모듈러 산술 표기법으로 표현하면, 함수 f는 다음과 같이 정의된다.

:

f(n) = \begin{cases} n/2 &\text{if } n \equiv 0 \pmod{2},\\[4px] 3n+1 & \text{if } n\equiv 1 \pmod{2} .\end{cases}

이 연산을 반복하여 수열을 만들고, 각 단계의 결과를 다음 단계의 입력으로 사용한다.

표기법:

:

a_i = \begin{cases}n & \text{for } i = 0, \\ f(a_{i-1}) & \text{for } i > 0 \end{cases}

(즉, 는 가 에 재귀적으로 번 적용된 값이다.)

n이 홀수일 때마다 3n + 1은 짝수이므로, 콜라츠 함수의 "단축" 형태를 대신 사용할 수 있다.

:

f(n) = \begin{cases} \frac{n}{2} &\text{if } n \equiv 0 \pmod{2},\\[4px] \frac{3n+1}{2} & \text{if } n\equiv 1 \pmod{2}. \end{cases}

2. 2. 추측 내용

임의의 양의 정수에 대해 다음 연산을 반복한다.

숫자가 짝수면 2로 나눈다.
숫자가 홀수면 3을 곱하고 1을 더한다.

모듈러 산술 표기법으로, 함수 f를 다음과 같이 정의한다.

:

f(n) = \begin{cases} n/2 &\text{if } n \equiv 0 \pmod{2},\\[4px] 3n+1 & \text{if } n\equiv 1 \pmod{2} .\end{cases}

이 연산을 반복하여 수열을 만들고, 각 단계의 결과를 다음 단계의 입력으로 사용한다.

:

a_i = \begin{cases}n & \text{for } i = 0, \\ f(a_{i-1}) & \text{for } i > 0 \end{cases}

(즉,

a_i

는

f

가

n

에 재귀적으로

i

번 적용된 값이다.)

콜라츠 추측은 다음과 같다: ''이 과정은 처음에 어떤 양의 정수를 선택하든 결국 1에 도달할 것이다.'' 즉, 모든

n

에 대해

a_i = 1

인

i

가 존재한다. 1에 도달한 후에는 1 → 4 → 2 → 1 의 순환이 반복된다.

만약 추측이 거짓이라면, 1을 포함하지 않는 수열을 생성하는 시작 숫자가 있기 때문일 수 있다. 이러한 수열은 1을 제외한 반복 주기에 들어가거나 무한대로 증가할 것이다. 그러한 수열은 발견되지 않았다.

n

이 홀수일 때마다

3n + 1

이 짝수이므로, 콜라츠 함수의 "단축" 형태를 대신 사용할 수 있다.

:

f(n) = \begin{cases} \frac{n}{2} &\text{if } n \equiv 0 \pmod{2},\\[4px] \frac{3n+1}{2} & \text{if } n\equiv 1 \pmod{2}. \end{cases}

2. 3. 수학적 표현

콜라츠 추측은 다음 함수 f(n)^영어으로 표현할 수 있다.

:

f(n)=\begin{Bmatrix}{n \over 2}, & \mbox{if }n\mbox{ is even} \\3n+1, & \mbox{if }n\mbox{ is odd} \end{Bmatrix}

n^영어이 홀수일 때 3n+1^영어은 항상 짝수이므로, 다음과 같이 표현하기도 한다.

:

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}

합동 산술을 사용하면 다음과 같이 표현할 수 있다.

:

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}

3. 역사

콜라츠 추측은 1930년대 독일 함부르크 대학교의 학생이었던 로타르 콜라츠가 처음 제기하였다.^[1] 1950년 국제 수학자 회의에서 이 문제를 언급하면서 널리 알려지게 되었다.^[1] 이후 여러 수학자들에 의해 연구되면서 다양한 이름으로 불리게 되었는데, 헬무트 하세의 이름을 따 "하세의 알고리즘", 시라큐스 대학교의 이름을 따 "시라큐스 문제", 카쿠타니 시즈오의 이름을 따 "카쿠타니의 문제", 스타니스와프 울람의 이름을 따 "울람의 문제"라고도 불린다.^[1]

콜라츠 추측의 해결에는 여러 현상금이 걸려 있었다.^[1] 콕세터는 50달러, 에르되시는 500달러, 브라이언 스웨이츠(Bryan Thwaites)는 1000파운드를 제시했다.^[1] 2021년 7월 7일, 주식회사 음압폭상군은 콜라츠 추측의 진위를 밝힌 사람에게 1.2억엔을 지불하겠다고 발표했다.

2019년, 테렌스 타오는 콜라츠 추측이 "거의 모든" 자연수에 대해 "거의" 옳다는 것을 증명했다.^[1]

4. 증명 시도와 관련된 논거

콜라츠 추측은 아직 증명되지 않았지만, 이 문제를 연구한 많은 수학자들은 실험적 증거와 발견적 논증을 통해 추측이 참일 것이라고 예상한다. 이 문제를 초창기 컴퓨터로 연구한 사람으로는 스타니스와프 울람이 있다.

4. 1. 실험적 증거

컴퓨터를 이용한 계산을 통해 2⁶⁸ ≈ 2.95×10²⁰까지의 모든 초기값에 대해 콜라츠 추측이 성립함이 확인되었다.^[41] 이 수치는 컴퓨터 속도 향상과 테스트 기술의 발전에 따라 계속 갱신되고 있다.

하지만 이러한 컴퓨터 검증은 추측이 참이라는 증거가 되지는 않는다. 포여 추측, Mertens conjecture|메르텐스 추측^영어, 스키우스 수의 경우에서 나타났듯이, 매우 큰 수에서 추측의 반례가 발견될 수 있다.

4. 2. 확률론적 휴리스틱

콜라츠 추측은 초기값이 짝수이면 2로 나누고, 홀수이면 3을 곱하고 1을 더하는 과정을 반복하면 결국 1에 도달한다는 추측이다. 이 섹션에서는 이러한 과정이 확률적으로 어떤 경향을 보이는지 살펴본다.

콜라츠 과정에서 홀수만 고려하면, 각 홀수는 다음 단계에서 평균적으로 이전 홀수의 3/4배가 된다. 예를 들어 어떤 홀수 n에 대해 다음 단계는 (3n + 1)/2가 되는데, 이는 평균적으로 3n/2의 절반, 즉 3n/4가 된다. 이러한 경향은 장기적으로 수열이 감소하는 방향으로 진행될 가능성이 높다는 것을 보여준다.

하지만 이는 각 단계가 서로 상관관계가 없는 독립적인 확률적 사건이라는 가정에 기반한다. 실제로는 각 단계가 이전 단계에 영향을 받으므로, 이는 엄밀한 증명이라고 할 수 없다.

스트렌마이어는 1957년에 마팅게일 이론을 사용하여, 임의의 콜모고로프 측도 하에서 유한 단계 내에 숫자의 크기가 1에 개수렴(확률 1로 수렴)한다는 것을 증명했다.^[41]

4. 3. 정지 시간

Riho Terras^영어의 증명에 따르면, 거의 모든 양의 정수는 유한한 정지 시간을 갖는다.^[32] 즉, 거의 모든 콜라츠 수열은 초기 값보다 엄격하게 낮은 지점에 도달한다. 이 증명은 패리티 벡터의 분포를 기반으로 하며 중심 극한 정리를 사용한다.

테렌스 타오는 2019년 이 결과를 개선하여, 로그 확률 밀도 함수를 사용하여, 시작점의 어떤 함수보다 아래로 내려가는 거의 모든(로그 밀도 의미에서) 콜라츠 궤도가 시작점의 함수가 어떻게 천천히 무한대로 발산하든 상관없이 존재함을 보였다.^[5]^[9] ''Quanta Magazine''은 타오가 "수십 년 동안 콜라츠 추측에 대한 가장 중요한 결과 중 하나를 얻었다"고 언급했다.^[5]^[9]

총 정지 시간이 가장 긴 시작 값은 다음과 같다.

범위	단계 수	시작 값
10 미만	19	9
100 미만	118	97
1000 미만	178	871
10⁴ 미만	261	6171
10⁵ 미만	350
10⁶ 미만	524
10⁷ 미만	685
10⁸ 미만	949
10⁹ 미만	986
10¹⁰ 미만	1132	^[6]
10¹¹ 미만	1228
10¹² 미만	1348	^[7]

이러한 숫자는 표시된 단계 수를 가진 가장 낮은 숫자이지만, 주어진 한계 미만의 유일한 숫자는 아닐 수 있다. 예를 들어 는 과 마찬가지로 1132단계를 거친다.

자릿수(2진수 기준)에 비해 총 정지 시간이 가장 작은 시작 값은 2의 거듭제곱인데, 이는 1에 도달하기 위해 해당 값만큼 번 반으로 줄어들고 결코 증가하지 않기 때문이다.

4. 4. 하한

컴퓨터 보조 증명을 통해, 크라시코프(Krasikov)와 라가리아스(Lagarias)는 충분히 큰 에 대해 구간 에서 1에 도달하는 정수의 개수가 최소 임을 보였다.^[10]

5. 순환 (Cycles)

n이 홀수일 때 3n + 1은 반드시 짝수가 되므로, 콜라츠 함수의 "단축" 형식은 다음과 같이 정의된다.

: $T(x) = \begin{cases} x/2 &\mbox{if } x \equiv 0 \pmod{2},\\ (3x+1)/2 & \mbox{if } x \equiv 1 \pmod{2}. \end{cases}$

콜라츠 수열의 '''순환'''(cycle)은 서로 다른 양의 정수로 구성된 수열 $(a_0, a_1, \ldots, a_q)$ 이며, $T(a_0)=a_1$ , $T(a_1)=a_2$ , ..., $T(a_q)=a_0$ 을 만족한다. 현재까지 알려진 유일한 순환은 길이 2의 $(1, 2)$ 이며, 이를 자명한 순환(trivial cycle)이라고 부른다.

5. 1. 순환 길이

비자명 순환의 길이는 최소 114,208,327,604 (단축 경로를 사용하지 않으면 186,265,759,595)로 알려져 있다.^[26]^[28] 만약 217,976,794,617 (단축 경로를 사용하지 않으면 355,504,839,929) 보다 작은 모든 양의 정수에 대해 콜라츠 수열이 1에 도달한다는 것을 보일 수 있다면, 이 경계는 더 증가할 것이다. 실제로, 엘리아후(Eliahou)는 1993년에 비자명 순환의 주기 p가 다음과 같은 형태임을 증명했다.

: p = 301994a + 17087915b + 85137581c

여기서 a, b, c는 음이 아닌 정수이고, b ≥ 1이며, ac = 0이다. 이 결과는 ln(3)/ln(2)의 연분수 전개에 기반한다.^[28]

최신 검증에 따르면, 2⁶⁸까지 콜라츠 추측이 옳다고 판명되었으므로, 유사한 논법에 따라 순환 길이의 하한은 114,208,327,604 (「숏컷」없이는 186,265,759,595)라고 할 수 있다.

5. 2. k-사이클

''k''-사이클은 홀수의 증가 수열 ''k''개와 짝수의 감소 수열 ''k''개, 총 2''k''개의 연속적인 부분 수열로 분할될 수 있는 사이클이다.^[31] 예를 들어, 사이클이 홀수의 단일 증가 수열과 짝수의 감소 수열로 구성된 경우 이를 ''1-사이클''이라고 한다.

슈타이너(1977)는 자명한 사이클 외에 1-사이클이 존재하지 않음을 증명했다.^[30] 존 L. 사이먼스(John L. Simons)는 슈타이너의 방법을 사용하여 2-사이클이 존재하지 않음을 증명했다.^[11] 시몬스와 데 베거(2005)는 이 증명을 68-사이클까지 확장했으며, ''k'' < 68 인 ''k''-사이클은 존재하지 않는다.^[31]

6. 다른 방식의 표현

콜라츠 추측은 추상 기계로 표현할 수 있다. 이 기계는 비트열의 문자열을 처리하며, 홀수에 대해 단 하나의 1이 남을 때까지 아래 세 단계를 수행한다.

1. 이진수 숫자(2''n'' + 1)의 끝(오른쪽)에 1을 추가한다.

2. 원래 숫자에 이진 덧셈을 통해 더한다 (2''n'' + 1 + ''n'' = 3''n'' + 1).

3. 모든 후행 0을 제거한다 (결과가 홀수가 될 때까지 반복해서 2로 나눈다).

예를 들어 7은 이진법으로 111로 표기되며, 결과 콜라츠 수열은 다음과 같다.

111

111'''1'''

10110

1011'''1'''

100010

10001'''1'''

110100

1101'''1'''

101000

101'''1'''

10000

6. 1. 역방향 접근

거꾸로 생성된 처음 21개 레벨의 ''콜라츠 그래프''. 그래프는 궤도 길이가 21 이하인 모든 숫자를 포함한다.

콜라츠 추측을 증명하는 또 다른 방법은, ''콜라츠 그래프''를 만드는 상향식 방법을 고려하는 것이다. ''콜라츠 그래프''는 다음 역 관계로 정의되는 그래프이다.

:

R(n) = \begin{cases} \{2n\} & \text{if } n\equiv 0,1,2,3,5 \\[4px] \left\{2n,\frac{n-1}{3}\right\} & \text{if } n\equiv 4 \end{cases} \pmod 6.

따라서, 모든 양의 정수가 결국 1로 이어진다는 것을 증명하는 대신, 1이 모든 양의 정수로 거꾸로 이어진다는 것을 증명하려고 할 수 있다. 모든 정수 n에 대해, n ≡ 1 (mod 2) 필요충분 조건은 3n + 1 ≡ 4 (mod 6)이다. 동등하게, (n − 1)/3 ≡ 1 (mod 2)는 n ≡ 4 (mod 6)일 때 필요충분 조건이다. 추측컨대, 이 역관계는 1–2–4 루프를 제외하고는 트리를 형성한다.^[12]

함수 f의 관계 3n + 1이 일반적인 "지름길" 관계 (3n + 1)/2로 대체될 때, 콜라츠 그래프는 다음 역관계로 정의된다.

:

R(n) = \begin{cases} \{2n\} & \text{if } n\equiv 0,1 \\[4px] \left\{2n,\frac{2n-1}{3}\right\} & \text{if } n\equiv 2 \end{cases} \pmod 3.

모든 정수 n에 대해, n ≡ 1 (mod 2)는 (3n + 1)/2 ≡ 2 (mod 3)일 때 필요충분 조건이다. 동등하게, (2n − 1)/3 ≡ 1 (mod 2)는 n ≡ 2 (mod 3)일 때 필요충분 조건이다. 추측컨대, 이 역관계는 1–2 루프를 제외하고는 트리를 형성한다.^[13]

6. 2. 패리티 시퀀스

Collatz parity sequence^영어는 콜라츠 함수의 단축 형태를 사용하여 정의한다.

:

f(n) = \begin{cases} \frac{n}{2} &\text{if } n \equiv 0 \\[4px] \frac{3n + 1}{2} & \text{if } n \equiv 1 \end{cases} \pmod{2}.

가 숫자의 패리티를 나타낼 때, 즉 이고 이면, 숫자 에 대한 콜라츠 패리티 시퀀스(또는 패리티 벡터)는 로 정의할 수 있다. 여기서 , 이다.

어떤 연산( 또는 )이 수행되는지는 패리티에 따라 달라진다. 패리티 시퀀스는 연산의 시퀀스와 동일하다.

에 이 형식을 사용하면, 두 숫자 과 의 패리티 시퀀스가 처음 개 항에서 일치하는 것과 과 이 를 법으로 합동인 것은 동치이다. 이는 모든 숫자가 패리티 시퀀스에 의해 고유하게 식별된다는 것을 의미하며, 또한 여러 하일스톤 사이클이 있는 경우 해당 패리티 사이클이 달라야 함을 의미한다.^[23]^[32]

함수를 숫자 에 번 적용하면 결과는 가 된다. 여기서 는 함수를 번 에 적용한 결과이고, 는 해당 시퀀스 동안 3배 연산(증가)이 발생한 횟수이다. 예를 들어, 의 경우 1이 2, 1, 2, 1로 반복되고 마지막으로 2가 되므로 3번의 증가가 있으므로 결과는 이다.

이러한 패리티 시퀀스의 성질을 이용하여 콜라츠 수열 계산 속도를 높일 수 있다. 단계 앞을 건너뛰려면, 현재 값을 (2진수 표기에서 하위 비트)와 (나머지 상위 비트)로 나눈다. 단계를 건너뛴 결과는 다음과 같다.

:

{f^k}\left(a\ {2^k}+b\right)=a\ {3^{c\left(b\right)}}+d\left(b\right)

.

여기서 (또는 )와 배열은 비트의 모든 수에 대해 미리 계산해 둔다. 는 에 함수를 번 적용한 수이고, 는 그 사이에 등장한 홀수의 수이다.^[49] 예를 들어 이면, 다음 배열을 사용하여 5단계를 건너뛸 수 있다.

:

c\left(0\dots31\right)=\left\{0,3,2,2,2,2,2,4,1,4,1,3,2,2,3,4,1,2,3,3,1,1,3,3,2,3,2,4,3,3,4,5\right\}

:

d\left(0\dots31\right)=\left\{0,2,1,1,2,2,2,20,1,26,1,10,4,4,13,40,2,5,17,17,2,2,20,20,8,22,8,71,26,26,80,242\right\}

이는 개의 사전 계산과 저장이 필요하며, 계산 속도를 배 빠르게 할 수 있지만, 시간-공간 트레이드 오프가 발생한다.

6. 3. 태그 시스템

콜라츠 수열은 생산 규칙을 사용하는 2-태그 시스템으로 계산할 수 있다. 해당 시스템의 규칙은 다음과 같다.^[44]

이 시스템에서 양의 정수 n은 a의 n개 문자열로 표현되며, 태그 연산의 반복은 길이가 2 미만인 단어에서 중단된다. 콜라츠 추측은 초기 단어로 a의 임의의 유한 문자열을 사용하여 이 태그 시스템이 결국 중단된다는 것과 동일하다.^[44]

7. 확장

콜라츠 추측은 음수를 포함하는 정수 전체와 홀수 분모를 가지는 유리수, 그리고 2진 정수로 확장할 수 있다.

정수 확장의 경우, 0 → 0 순환을 제외하면 모든 0이 아닌 정수는 다음 4개의 순환 중 하나로 수렴하는 것으로 보인다.

순환	홀수 값 순환 길이	전체 순환 길이
1 → 4 → 2 → 1 ...	1	3
−1 → −2 → −1 ...	1	2
−5 → −14 → −7 → −20 → −10 → −5 ...	2	5
−17 → −50 → −25 → −74 → −37 → −110 → −55 → −164 → −82 → −41 → −122 → −61 → −182 → −91 → −272 → −136 → −68 → −34 → −17 ...	7	18

각 순환은 절댓값이 가장 작은 홀수로 시작하며, 홀수 값은 굵게 표시되어 있다. 일반화된 콜라츠 추측은 모든 정수가 이 4개의 순환 중 하나 또는 0 → 0 순환으로 수렴한다는 것이다.

콜라츠 맵은 기약분수로 나타낼 때 홀수 분모를 갖는 유리수로 확장할 수 있다. '짝수' 유리수는 2로 나누고, '홀수' 유리수는 3을 곱한 다음 1을 더한다. 콜라츠 맵의 "단축" 정의를 사용하면, 모든 주기적인 패리티 수열은 정확히 하나의 유리수에 의해 생성된다.^[14] 반대로, 홀수 분모를 갖는 모든 유리수는 결국 순환적인 패리티 수열을 가질 것으로 추측된다 (주기성 추측^[23]).

패리티 사이클의 길이가 $n$이고, 인덱스 $k_0 < \cdots < k_{m-1}$에서 홀수가 정확히 $m$번 포함되어 있다면, 이 패리티 사이클을 즉시 그리고 주기적으로 생성하는 고유한 유리수는 다음과 같다.

: $\frac{3^{m-1} 2^{k_0} + \cdots + 3^0 2^{k_{m-1}}}{2^n - 3^m}.$

예를 들어 패리티 사이클 (1 0 1 1 0 0 1)은 길이가 7이고 인덱스 0, 2, 3, 6에서 4개의 홀수 항을 가지므로, 반복적으로 생성되는 분수는 다음과 같다.

: $\frac{3^3 2^0 + 3^2 2^2 + 3^1 2^3 + 3^0 2^6}{2^7 - 3^4} = \frac{151}{47}$

이는 유리수 사이클 $\frac{151}{47} \rightarrow \frac{250}{47} \rightarrow \frac{125}{47} \rightarrow \frac{211}{47} \rightarrow \frac{340}{47} \rightarrow \frac{170}{47} \rightarrow \frac{85}{47} \rightarrow \frac{151}{47}$ 로 이어진다.

콜라츠 추측이 참이라면, (1 0)과 (0 1)이 양의 정수에 의해 생성된 유일한 패리티 사이클이다.

또한 콜라츠 맵은 2진 정수의 환으로 확장될 수 있다. 2진 정수에는 홀수 분모를 갖는 유리수의 환이 부분환으로 포함되어 있다.

7. 1. 정수 전체로의 확장

콜라츠 추측은 음수를 포함한 모든 정수로 확장할 수 있다. 0 → 0 순환을 제외하면, 모든 0이 아닌 정수는 다음 4개의 순환 중 하나로 수렴하는 것으로 보인다.

순환	홀수 값 순환 길이	전체 순환 길이
1 → 4 → 2 → 1 ...	1	3
−1 → −2 → −1 ...	1	2
−5 → −14 → −7 → −20 → −10 → −5 ...	2	5
−17 → −50 → −25 → −74 → −37 → −110 → −55 → −164 → −82 → −41 → −122 → −61 → −182 → −91 → −272 → −136 → −68 → −34 → −17 ...	7	18

각 순환은 절댓값이 가장 작은 홀수로 시작하며, 홀수 값은 굵게 표시되어 있다. 일반화된 콜라츠 추측은 모든 정수가 이 4개의 순환 중 하나 또는 0 → 0 순환으로 수렴한다는 것이다.

7. 2. 홀수 분모를 갖는 유리수로의 확장

콜라츠 맵은 기약분수로 나타낼 때 홀수 분모를 갖는 (양수 또는 음수) 유리수까지 확장될 수 있다. 이때, 수는 분자가 홀수인지 짝수인지에 따라 '홀수' 또는 '짝수'로 간주된다. '짝수' 유리수는 2로 나누고, '홀수' 유리수는 3을 곱한 다음 1을 더한다.

콜라츠 맵의 "단축" 정의를 사용하면, 모든 주기적인 패리티 수열은 정확히 하나의 유리수에 의해 생성된다.^[14] 반대로, 홀수 분모를 갖는 모든 유리수는 결국 순환적인 패리티 수열을 가질 것으로 추측된다 (주기성 추측^[23]).

패리티 사이클의 길이가 $n$이고, 인덱스 $k_0 < \cdots < k_{m-1}$에서 홀수가 정확히 $m$번 포함되어 있다면, 이 패리티 사이클을 즉시 그리고 주기적으로 생성하는 고유한 유리수는 다음과 같다.

:

\frac{3^{m-1} 2^{k_0} + \cdots + 3^0 2^{k_{m-1}}}{2^n - 3^m}.

예를 들어, 패리티 사이클 (1 0 1 1 0 0 1)은 길이가 7이고 인덱스 0, 2, 3, 6에서 4개의 홀수 항을 갖는다. 이 분수는 반복적으로 생성된다.

:

\frac{3^3 2^0 + 3^2 2^2 + 3^1 2^3 + 3^0 2^6}{2^7 - 3^4} = \frac{151}{47}

이는 다음과 같은 유리수 사이클로 이어진다.

:

\frac{151}{47} \rightarrow \frac{250}{47} \rightarrow \frac{125}{47} \rightarrow \frac{211}{47} \rightarrow \frac{340}{47} \rightarrow \frac{170}{47} \rightarrow \frac{85}{47} \rightarrow \frac{151}{47} .

(1 0 1 1 0 0 1)의 모든 순환적 순열은 위의 분수 중 하나와 연관된다. 예를 들어, 사이클 (0 1 1 0 0 1 1)는 다음 분수에 의해 생성된다.

:

\frac{3^3 2^1 + 3^2 2^2 + 3^1 2^5 + 3^0 2^6}{2^7 - 3^4} = \frac{250}{47} .

일대일 대응을 위해서는 패리티 사이클이 "기약"해야 한다. 즉, 동일한 하위 사이클로 분할할 수 없어야 한다.

이 맥락에서 콜라츠 추측이 참이라면, (1 0)과 (0 1)이 양의 정수(각각 1과 2)에 의해 생성된 유일한 패리티 사이클임을 의미한다.

유리수의 홀수 분모 $d$가 3의 배수가 아닌 경우, 모든 반복은 동일한 분모를 가지며, 분자 수열은 콜라츠 함수의 $3n + d$ 일반화^[29]를 적용하여 얻을 수 있다.

:

T_d(x) = \begin{cases}\frac{x}{2} &\text{if } x \equiv 0 \pmod{2},\\[4px]\frac{3x+d}{2} & \text{if } x\equiv 1 \pmod{2}.\end{cases}

7. 3. 2진 정수로의 확장

Collatz map^영어은 기약 분수로 나타낼 때 홀수 분모를 갖는 (양수 또는 음수) 유리수까지 확장될 수 있다. 이때 수는 분자가 홀수인지 짝수인지에 따라 '홀수' 또는 '짝수'로 간주된다. 맵의 공식은 정의역이 정수일 때와 동일하다. 즉, '짝수' 유리수는 2로 나누고, '홀수' 유리수는 3을 곱한 다음 1을 더한다. 이와 밀접하게 관련된 사실은 콜라츠 맵이 2진 정수의 환으로 확장된다는 것이다. 2진 정수에는 홀수 분모를 갖는 유리수의 환이 부분환으로 포함되어 있다.

T(x) = \begin{cases} \frac{x}{2} &\text{if } x \equiv 0 \pmod{2}\\[4px] \frac{3x+1}{2} & \text{if } x \equiv 1 \pmod{2} \end{cases}

위 함수는 2진 정수의 환

\mathbb{Z}_2

에서 잘 정의되며, 여기서 연속적이고 2진 척도에 대해 측도 보존 변환이다. 게다가, 그 역학은 에르고딕 이론으로 알려져 있다.^[23]

8. 계산 복잡도

콜라츠 추측 및 관련 추측은 계산 복잡도 연구에 자주 사용된다.^[21]^[22] 이러한 연관성은 바쁜 비버 함수를 통해 이루어지는데, 여기서 BB(n)은 중단되는 모든 n 상태 튜링 기계가 수행하는 최대 단계 수이다. 폴 에르되시의 추측(콜라츠 추측과 밀접하게 관련됨)이 거짓일 때 중단되는 15 상태 튜링 기계가 존재한다. 따라서 BB(15)가 알려져 있고 이 기계가 해당 단계 수에서 멈추지 않는다면, 영원히 실행될 것이므로 반례가 존재하지 않아 추측이 참임이 증명된다. 이는 추측을 해결하는 완전히 비실용적인 방법이지만, BB(15)를 계산하는 것이 적어도 이 콜라츠 추측과 유사한 추측을 해결하는 것만큼 어려울 것이라는 점을 시사한다.

9. 유사 문제 및 일반화

패리티 시퀀스 섹션에서는 시퀀스 시뮬레이션을 가속화하는 방법을 제시한다. 각 반복에서 k 단계씩 건너뛰기 위해, 현재 숫자를 두 부분으로 나눈다. b는 가장 낮은 k 비트(정수로 해석)이고, a는 나머지 비트(정수로 해석)이다. k 단계를 건너뛴 결과는 다음과 같다.

:

c (또는 3^''c'')와 d의 값은 가능한 모든 k 비트 숫자 b에 대해 미리 계산할 수 있다. 여기서 d(''b'', ''k'')는 b에 f 함수를 k번 적용한 결과이고, c(''b'', ''k'')는 그 과정에서 만난 홀수의 개수이다.^[16] 예를 들어, k = 5인 경우, 숫자의 가장 낮은 5비트를 분리하고 다음을 사용하여 각 반복에서 5단계를 건너뛸 수 있다.

: c(0...31, 5) = { 0, 3, 2, 2, 2, 2, 2, 4, 1, 4, 1, 3, 2, 2, 3, 4, 1, 2, 3, 3, 1, 1, 3, 3, 2, 3, 2, 4, 3, 3, 4, 5 }

: d(0...31, 5) = { 0, 2, 1, 1, 2, 2, 2, 20, 1, 26, 1, 10, 4, 4, 13, 40, 2, 5, 17, 17, 2, 2, 20, 20, 8, 22, 8, 71, 26, 26, 80, 242 }

이는 2^''k''의 사전 계산 및 저장 공간을 필요로 하며, 결과 계산 속도를 k배로 높이는 시공간 트레이드오프이다.

함수 f의 정의를 약간 변경하여 콜라츠 문제의 유사 문제를 생각해 볼 수 있다.

9. 1. 변수 n이 홀수일 때 곱하는 수를 홀수 일반으로 확장

홀수에 곱하는 수를 3이 아닌 다른 홀수로 확장하는 경우를 생각할 수 있다. 이러한 경우, 1을 포함하지 않는 반복 수열이나 무한히 증가하는 수열이 발생할 수 있다.^[16]

예를 들어, 함수 f(n)을 다음과 같이 정의한다.

조건	연산
n이 짝수	n / 2
n이 홀수	m * n + 1 (m은 홀수)

m = 1 인 경우: n이 짝수이면 n / 2, 홀수이면 n + 1 이 된다. 이 경우, 2의 배수 안에 존재하는 값만이 만들어지므로, n의 범주를 넘지 못한 채 반복 수렴하여 1에 귀결된다.

m = 2 인 경우: n이 짝수이면 n / 2, 홀수이면 2n + 1이 된다. n이 홀수일 때 2가 곱해지면 항상 짝수가 되고, 여기에 1을 더하면 계속해서 무한히 증가하는 홀수가 만들어진다. 따라서 콜라츠 추측의 단계는 작동하지 않는다.

m ≥ 3인 경우에는, m의 값과 n의 초기값에 따라 1을 포함하지 않는 반복 수열이나 걷잡을 수 없이 증가하는 수열이 나타나므로, "유한 번에 1에 도달한다"라는 명제는 일반적으로 성립하지 않는다. 예를 들어 m = 3이고 n의 초기값이 13인 경우, 13, 66, 33, 166, 83, 416, 208, 104, 52, 26, 13과 같이 1을 포함하지 않는 순환 수열이 만들어진다.^[17]

9. 2. 변수 n이 홀수일 때 더하는 수를 홀수 일반으로 확장

Collatz conjecture^영어에서는 n이 홀수일 때 더하는 수를 1이 아닌 다른 홀수로 확장하는 경우에도 유사한 문제가 발생할 수 있다.

예를 들어, n이 홀수일 때 3n + 1 대신 3n + (2l - 1) (l ≥ 1) 연산을 하는 경우를 생각해 볼 수 있다. l = 1이면 원래의 콜라츠 추측과 같지만, l ≥ 2 이면 1을 포함하지 않는 반복 수열이 나타날 수 있다.

l = 2이고 초기값 n = 43인 경우: 43, 132, 66, 33, 102, 51, 156, 78, 39, 120, 60, 30, 15, 48, 24, 12, 6, 3, 12, 6, 3, ... 과 같이 3, 12, 6, 3이 반복되는 순환 수열이 나타난다.

이러한 경우, "임의의 양의 정수 n에 대해, 위의 연산을 수행하면 유한 번 안에 1 또는 3에 도달한다" 와 같이 명제를 수정하면 참이 될 것으로 예상된다.

일반적으로, "임의의 양의 정수 n에 대해, n이 짝수이면 n/2, 홀수이면 3n + (2l - 1) (l ≥ 1) 연산을 반복하면 유한 번 안에 1 또는 2l - 1 (l ≥ 1)에 도달한다"는 명제는 l ≥ 3 이상인 경우에는 성립하지 않을 수 있다. 예를 들어 l = 3, n = 13인 경우 19를 반복하는 무한 루프가 발생한다.

하지만, 2l - 1 (l ≥ 1)이 0 이상의 정수 a를 사용하여 3^a-1 (a ≥ 1)로 표현될 때에는, 유한 번 안에 1 또는 3^a-1 (a ≥ 1)에 도달할 것이라고 추측된다.

더 나아가, "임의의 양의 정수 n에 대해, n이 짝수이면 n/2, 홀수이면 (2m - 1)n + (2l - 1) (m ≥ 1, l ≥ 1) 연산을 반복할 때, n, m, l의 값에 따라 어떤 수열이 나타나는가" 라는 문제로 확장할 수 있다.

9. 3. 결정 불가능한 일반화 (콘웨이)

1972년, 존 호턴 콘웨이는 콜라츠 문제의 일반화가 알고리즘적으로 결정 불가능한 문제임을 증명했다.^[18]

콘웨이는 다음과 같은 형태의 함수를 고려했다.

: ''g''(''n'') = ''a''_''i''''n'' + ''b''_''i'' (''n''≡''i'' (mod ''P''))

여기서 ''a''₀, ''b''₀, ..., ''a''_{''P'' − 1}, ''b''_{''P'' − 1}는 ''g''(''n'')이 항상 정수가 되도록 선택된 유리수이다. 표준 콜라츠 함수는 ''P'' = 2, ''a''₀ = 1/2, ''b''₀ = 0, ''a''₁ = 3, ''b''₁ = 1로 주어진다. 콘웨이는 다음 문제를 통해 정지 문제를 표현함으로써 결정 불가능함을 증명했다.

: 주어진 ''g''와 ''n''에 대해, 반복 수열 ''g''^''k''(''n'')이 1에 도달하는가?

콜라츠 문제에 더 가까운 문제는 다음과 같은 "전칭 한정" 문제이다.

: 주어진 ''g''에 대해, 반복 수열 ''g''^''k''(''n'')이 모든 ''n'' > 0에 대해 1에 도달하는가?

Kurtz와 Simon은 전칭 한정 문제가 실제로 결정 불가능하며, 심지어 산술적 위계에서 더 높은 단계에 있다는 것을 증명했다.^[19] 구체적으로, 이는 Π⁰₂-완전이다. 이러한 어려움의 결과는 모듈 ''P''를 6480으로 고정하여 함수 ''g''의 클래스를 제한하더라도 유효하다.^[20]

모든 ''b''_''i''가 0인 이 형태의 단순화된 버전에서 ''g''의 반복은 난해한 프로그래밍 언어인 FRACTRAN에서 공식화된다.

참조

_[1] 서적 Logo: A Retrospective Haworth Press
_[2] 웹사이트 Lothar Collatz
_[3] 서적 Wonders of Numbers https://archive.org/[...] Oxford University Press
_[4] 서적 Gödel, Escher, Bach Basic Books
_[5] 간행물 Almost all orbits of the Collatz map attain almost bounded values 2022
_[6] 간행물 3''x'' + 1 search programs 1992-12
_[7] 웹사이트 3x+1 delay records http://www.ericr.nl/[...] 2020-03-14
_[8] 간행물 Convergence verification of the Collatz problem
_[9] 웹사이트 Mathematician Proves Huge Result on 'Dangerous' Problem https://www.quantama[...] 2019-12-11
_[10] 간행물 Bounds for the 3''x'' + 1 problem using difference inequalities https://www.impan.pl[...]
_[11] 간행물 On the nonexistence of 2-cycles for the 3''x'' + 1 problem
_[12] 간행물 The convergence classes of Collatz function 2011-09-09
_[13] 간행물 Working in binary protects the repetends of 1/3^''h'': Comment on Colussi's 'The convergence classes of Collatz function' 2016-03-07
_[14] 간행물 The set of rational cycles for the 3x+1 problem https://eudml.org/do[...] 1990
_[15] 간행물 The 3''x'' + 1 conjugacy map 1996
_[16] 웹사이트 Looking for class records in the 3''x'' + 1 problem by means of the COMETA grid infrastructure http://www.dmi.unict[...]
_[17] 웹사이트 The Long Search for Collatz Counterexamples https://scholarship.[...] 2024-07-26
_[18] conference Proc. 1972 Number Theory Conf., Univ. Colorado, Boulder
_[19] 서적 Proceedings of the 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007, held in Shanghai, China in May 2007
_[20] 간행물 Mortality of iterated piecewise affine functions over the integers: Decidability and complexity
_[21] 간행물 Busy beaver competition and Collatz-like problems
_[22] 웹사이트 Hardness of busy beaver value BB(15) https://arxiv.org/ht[...]
_[23] 간행물 The 3''x'' + 1 problem and its generalizations
_[24] 간행물 A continuous extension of the 3''x'' + 1 problem to the real line
_[25] 간행물 On the Collatz 3''n'' + 1 algorithm
_[26] 간행물 There are no Collatz ''m''-cycles with ''m <= 91'' https://cs.uwaterloo[...]
_[27] 간행물 The (3''n'' + 1)-problem and holomorphic dynamics
_[28] 간행물 The 3''x'' + 1 problem: new lower bounds on nontrivial cycle lengths
_[29] 간행물 Embedding the 3x+1 Conjecture in a 3x+d Context http://www.emis.de/j[...]
_[30] 서적 Proceedings of the 7th Manitoba Conference on Numerical Mathematics
_[31] 간행물 Theoretical and computational bounds for ''m''-cycles of the 3''n'' + 1 problem http://deweger.xs4al[...] 2023-03-28
_[32] 간행물 A stopping time problem on the positive integers http://matwbn.icm.ed[...]
_[33] 서적 Unsolved Problems in Number Theory Springer-Verlag
_[34] 서적 The Ultimate Challenge: The 3''x'' + 1 Problem American Mathematical Society
_[35] 간행물 Almost all orbits of the Collatz map attain almost bounded values
_[36] PDF 수학Ⅱ・数学B（2011年1月24日時点のインターネットアーカイブ） https://web.archive.[...]
_[37] 웹사이트 Almost all orbits of the Collatz map attain almost bounded values https://arxiv.org/ab[...] arXiv 2019-09-08
_[38] 뉴스 Mathematician Proves Huge Result on ‘Dangerous’ Problem https://www.quantama[...] 2019-12-11
_[39] 웹사이트 コラッツ予想懸賞金1億2000万円 https://mathprize.ne[...] Mathprize 2021-07-07
_[40] 웹사이트 数学者も恐れる「ハマると病む難問」解けたら1億円、企業が懸賞金 https://www.asahi.co[...] 朝日新聞社 2021-09-24
_[41] 간행물 Convergence verification of the Collatz problem
_[42] 간행물 The 3x+1 problem: new lower bounds on nontrivial cycle lengths 1993-08-01
_[43] 간행물 On the nonexistence of 2-cycles for the 3x+1 problem
_[44] 간행물 The 3x + 1 problem and its generalizations
_[45] 간행물 A stopping time problem on the positive integers http://matwbn.icm.ed[...]
_[46] 간행물 The set of rational cycles for the 3x+1 problem https://eudml.org/do[...] 1990
_[47] 간행물 Una actualització del problema 3x + 1 http://revistes.iec.[...]
_[48] 웹사이트 An Update on the 3x+1 Problem https://chamberland.[...] Marc Chamberland
_[49] 간행물 Grid Open Days at the University of Palermo http://www.dmi.unict[...]
_[50] 간행물 On the Collatz 3𝑛+1 algorithm https://www.ams.org/[...] 1981
_[51] 간행물 A continuous extension of the 3''x'' + 1 problem to the real line
_[52] 간행물 The (3''n'' + 1)-Problem and Holomorphic Dynamics
_[53] 서적 Proceedings of the 7th Manitoba Conference on Numerical Mathematics
_[54] 간행물 Theoretical and computational bounds for ''m''-cycles of the 3''n'' + 1 problem http://deweger.xs4al[...]
_[55] 뉴스 Convergence verification of the Collatz problem https://doi.org/10.1[...] J Supercomput 2020

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com