콜라츠 추측

콜라츠 추측(Collatz conjecture)은 수학의 가장 유명한 미해결 문제 중 하나로, 두 가지 간단한 산술 연산을 반복하면 모든 양의 정수가 결국 1로 변환되는지에 관한 것이다. 이 문제에서는 각 항이 이전 항에서 두 가지 규칙을 통해 얻어지는 정수열을 다루며, 만약 항이 짝수이면 다음 항은 그것의 절반이고, 홀수이면 다음 항은 이전 항의 3배에 1을 더한 값이다. 이 추측이 참일 경우 어떤 양의 정수를 시작으로 선택하든 이 수열이 항상 1에 도달한다. 이 추측은 까지의 모든 양의 정수에 대해 성립함이 입증되었지만, 일반적인 증명은 아직 발견되지 않았다.

이 추측은 1937년 박사 학위를 받은 지 2년 후 이 아이디어를 제시한 수학자 로타르 콜라츠의 이름을 따서 명명되었다. 관련된 숫자열은 때때로 우박 수열, 우박 숫자 또는 우박수(값들이 구름 속의 우박처럼 여러 번 상승과 하강을 겪기 때문), 경이로운 숫자라고도 불린다.

에르되시 팔은 콜라츠 추측에 대해 "수학은 이러한 문제에 준비되지 않았을지도 모른다"라고 말했다. 제프리 라가리아스는 2010년에 콜라츠 추측이 "극도로 어려운 문제이며, 현재 수학으로는 완전히 도달할 수 없다"고 언급했다. 콜라츠 추측 자체는 아직 미해결로 남아 있지만, 이 문제를 해결하려는 노력은 새로운 기법과 많은 부분 해결법을 낳았다.

 문제의 진술 
alt=총 정지 시간: 250, 1000, 4000, 20000, 100000, 500000까지의 숫자|thumb|250, 1000, 4000, 20000, 100000, 500000까지의 숫자에 대한 총 정지 시간
임의의 양의 정수에 대한 다음 연산을 고려한다.

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

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

이제 어떤 양의 정수로부터 시작하여 이 연산을 반복적으로 수행하고, 각 단계의 결과를 다음 단계의 입력으로 삼아 수열을 형성한다.

표기법으로는 다음과 같다.

(즉: 는 를 에 번 재귀적으로 적용한 값이 )이다.

콜라츠 추측은 이 과정을 처음에 어떤 양의 정수를 선택하든 결국 숫자 1에 도달한다는 말이다. 즉, 각 에 대해 인 어떤 가 존재한다.

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

를 만족하는 가장 작은 를 의 정지 시간이라고 한다. 비슷하게, 을 만족하는 가장 작은 를 의 총 정지 시간이라고 한다. 만약  또는  인덱스 중 하나가 존재하지 않으면, 정지 시간 또는 총 정지 시간은 각각 무한하다고 말한다.

콜라츠 추측은 모든 의 총 정지 시간이 유한하다고 주장한다. 이는 모든 가 유한한 정지 시간을 가진다는 것과 동등하다.

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

이 정의는 과정의 전체적인 역학을 변경하지 않고 정지 시간과 총 정지 시간에 대해 더 작은 값을 산출한다.

 경험적 자료 
예를 들어, 에서 시작하여 "단축" 없이 함수 를 적용하면 수열 를 얻는다.

숫자 는 1에 도달하는 데 더 오래 걸린다: .

아래에 나열되고 그래프화된 에 대한 수열은 111단계를 거쳐 (굵게 표시된 홀수는 41단계), 1로 내려가기 전에 9232까지 올라간다.




어떤 작은 시작 값보다 총 정지 시간이 더 긴 숫자는 다음과 같은 수열로 시작한다.
1, 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171, ... .

최대 궤적 지점이 어떤 작은 시작 값보다 큰 시작 값은 다음과 같다.
1, 2, 3, 7, 15, 27, 255, 447, 639, 703, 1819, 4255, 4591, 9663, 20895, 26623, 31911, 60975, 77671, 113383, 138367, 159487, 270271, 665215, 704511, ... 

이 1에 도달하는 데 걸리는 단계 수는 다음과 같다.
0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20, 7, 7, 15, 15, 10, 23, 10, 111, 18, 18, 18, 106, 5, 26, 13, 13, 21, 21, 21, 34, 8, 109, 8, 29, 16, 16, 16, 104, 11, 24, 24, ... 

총 정지 시간이 가장 길지만 주어진 한계 미만인 시작 값은 다음과 같다.
10 미만은 9이며, 19단계,
100 미만은 97이며, 118단계,
1000 미만은 871이며, 178단계,
104 미만은 6171이며, 261단계,
105 미만은 이며, 350단계,
106 미만은 이며, 524단계,
107 미만은 이며, 685단계,
108 미만은 이며, 949단계,
109 미만은 이며, 986단계,
1010 미만은 이며, 1132단계,
1011 미만은 이며, 1228단계,
1012 미만은 이며, 1348단계이다. (참고: "지연 기록"은 총 정지 시간 기록이다.) 

이 숫자들은 표시된 단계 수를 가진 가장 낮은 숫자이지만, 주어진 한계 미만의 유일한 숫자는 아니다. 예를 들어, 은 1132단계를 가지며, 도 마찬가지이다.

자리수 (2진법)에 대한 총 정지 시간이 가장 작은 시작 값은 2의 거듭제곱이다. 이는 이 1에 도달하기 위해 번 절반으로 줄어들고, 절대로 증가하지 않기 때문이다.

 시각화 

 지지 논거 
이 추측은 아직 증명되지 않았지만, 이 문제를 연구한 대부분의 수학자는 실험적 증거와 휴리스틱 논거가 이를 지지하기 때문에 이 추측이 참이라고 생각한다.

 실험적 증거 
이 추측은 271 ≈ 까지의 모든 시작 값에 대해 컴퓨터로 확인되었다. 지금까지 테스트된 모든 값은 1로 수렴한다.

이 컴퓨터 증거는 모든 시작 값에 대해 추측이 참이라는 엄격한 증명은 아니다. 폴리아 추측과 메르텐스 추측이 반증된 경우처럼, 매우 큰 (또는 엄청난) 양의 정수를 고려한다면 반례가 발견될 수도 있기 때문이다.

그러나 이러한 검증은 다른 함의를 가질 수 있다. 비자명 순환에 대한 특정 제약, 예를 들어 순환 길이의 하한은 순환의 최저 항 값에 기초하여 증명될 수 있다. 따라서 작은 최저 항을 가진 순환을 배제하기 위한 컴퓨터 탐색은 이러한 제약을 강화할 수 있다.

 확률적 휴리스틱 
콜라츠 과정에 의해 생성된 수열에서 홀수만 고려하면, 각 홀수는 평균적으로 이전 홀수의 이다. (더 정확히 말하면, 결과 비율의 기하 평균은 이다.) 이는 모든 우박 수열이 장기적으로는 감소해야 한다는 휴리스틱 논거를 제시하지만, 이는 다른 순환에 대한 증거가 아니라 발산에 대한 증거일 뿐이다. 이 논거는 우박 수열이 상관 관계가 없는 확률적 사건으로 구성된다고 가정하기 때문에 증명이 아니다. (이는 콜라츠 과정의 2-진 확장이 거의 모든 2-진 시작 값에 대해 모든 곱셈 단계마다 두 개의 나눗셈 단계를 가진다는 것을 엄격하게 입증한다.)

 정지 시간 
리호 테라스에 의해 증명된 바와 같이, 거의 모든 양의 정수는 유한한 정지 시간을 갖는다. 즉, 거의 모든 콜라츠 수열은 초기 값보다 엄격히 작은 지점에 도달한다. 이 증명은 홀짝성 벡터의 분포에 기반하며 중심 극한 정리를 사용한다.

2019년에 테런스 타오는 이 결과를 개선하여 밀도를 사용하여 거의 모든 (로그 밀도 의미에서) 콜라츠 궤도가 시작점의 주어진 함수 아래로 감소한다는 것을 보였다. 이 함수가 아무리 느리게 무한대로 발산하더라도 말이다. 이 연구에 대해 콴타매거진은 타오가 "수십 년 만에 콜라츠 추측에 대한 가장 중요한 결과 중 하나를 얻었다"고 썼다.

 하한 
컴퓨터 보조 증명에서 크라시코프와 라가리아스는  구간에 있는 정수 중 결국 1에 도달하는 숫자의 수가 모든 충분히 큰 에 대해 최소한 와 같다는 것을 보였다.

 순환 
이 부분에서는 콜라츠 함수의 단축 형태를 고려한다.

순환은 구별되는 양의 정수의 수열 이며, 여기서 , , ..., 그리고 이다.

유일하게 알려진 순환은 주기 2의 이며, 이를 자명 순환이라고 한다.

 순환 길이 
비자명 순환의 길이는 최소  (단축이 없을 경우 )로 알려져 있다. 만약  미만의 모든 양의 정수에 대해 콜라츠 수열이 1에 도달함을 보일 수 있다면, 이 하한은  (단축이 없을 경우 )로 올라갈 것이다. 실제로, 엘리아후(1993)는 어떤 비자명 순환의 주기 가 다음 형태를 가진다는 것을 증명했다.

여기서 ,  및 는 음이 아닌 정수이고, 이며 이다. 이 결과는 의 단순 연분수 전개에 기반한다.

-순환 
-순환은 개의 연속적인 부분 수열로 나눌 수 있는 순환이며, 각 부분 수열은 증가하는 홀수열과 그 뒤를 잇는 감소하는 짝수열로 구성된다. 예를 들어, 순환이 단일 증가하는 홀수열과 그 뒤를 잇는 감소하는 짝수열로 구성된다면, 이를 1-순환이라고 부른다.

슈타이너(1977)는 자명한  외에는 1-순환이 없음을 증명했다. 시몬스(2005)는 슈타이너의 방법을 사용하여 2-순환이 없음을 증명했다. 시몬스와 드 베거(2005)는 이 증명을 68-순환까지 확장했다. 까지는 -순환이 존재하지 않는다. 헤르셔는 이 방법을 더욱 확장하여 인 k-순환이 존재하지 않음을 증명했다. 철저한 컴퓨터 탐색이 계속됨에 따라, 더 큰  값도 배제될 수 있다. 주장을 더 직관적으로 표현하자면, 각 부분 수열이 연속적인 상승 다음에 연속적인 하강으로 구성되는, 92개 미만의 부분 수열을 가진 순환을 찾을 필요는 없다.

 추측의 다른 공식화 

 역방향으로 

이 추측을 증명하는 또 다른 접근 방식은 콜라츠 그래프라고 불리는 것을 바텀업 방식으로 성장시키는 것을 고려하는 것이다. 콜라츠 그래프는 다음 역관계에 의해 정의되는 그래프이다.

따라서, 모든 양의 정수가 결국 1에 이른다는 것을 증명하는 대신, 1이 모든 양의 정수로 역방향으로 이어진다는 것을 증명하려고 시도할 수 있다. 어떤 정수 에 대해, 는 인 동치이다. 동등하게, 는 인 경우에만 그렇다. 추측적으로, 이 역관계는 1–2–4 루프(이 글의 문제의 진술 절에서 정의된 변경되지 않은 함수 의 4–2–1 루프의 역)를 제외하고는 나무를 형성한다.

함수 의  관계가 일반적인 "단축" 대체 관계인 로 대체될 때, 콜라츠 그래프는 역관계로 정의된다.

어떤 정수 에 대해, 는 인 경우에만 그렇다. 동등하게, 는 인 경우에만 그렇다. 추측적으로, 이 역관계는 1–2 루프(위에서 언급된 대로 수정된 함수 f(n)의 1–2 루프의 역)를 제외하고는 나무를 형성한다.

대안적으로, 을 로 대체한다. 여기서 이고 은 을 나누는 가장 큰 2의 거듭제곱이다 (나머지 없음). 결과 함수 는 홀수에서 홀수로 매핑된다. 이제 어떤 홀수 에 대해 이 연산을 번 적용하여 숫자 1을 얻는다고 가정한다 (즉, ). 그러면 이진수로 숫자 은 문자열 의 연결로 쓸 수 있다. 여기서 각 는 의 표현에서 유한하고 연속적인 추출물이다. 따라서 의 표현은 의 순환 부분을 포함하며, 각 순환 부분은 선택적으로 회전되고 유한한 비트 수까지 복제된다. 이는 오직 이진법에서만 발생한다. 추측적으로, '1'로 끝나는 모든 이진 문자열 는 이 형태의 표현(여기서 에 선행 '0'을 추가하거나 삭제할 수 있다)으로 도달할 수 있다.

 이진수로 계산하는 추상 기계로서 
콜라츠 함수를 반복적으로 적용하는 것은 비트 문자열을 처리하는 추상 기계로 나타낼 수 있다. 이 기계는 하나의 이 남을 때까지 어떤 홀수에 대해 다음 세 단계를 수행한다.

 이진수로 숫자의 (오른쪽) 끝에 을 추가한다 ().
 이진 덧셈으로 원래 숫자에 이 값을 더한다 ().
 모든 후행 을 제거한다 (즉, 결과가 홀수가 될 때까지 반복적으로 2로 나눈다).

 예시 
시작 숫자 7은 이진수로 로 쓰여진다. 결과 콜라츠 수열은 다음과 같다.

          111
         1111
        10110
       10111
      100010
     100011
     110100
    11011
   101000
  1011
 10000

 홀짝성 수열로서 
이 절에서는 콜라츠 함수의 단축 형태를 고려한다.

만약 가 어떤 숫자의 홀짝성을 나타내는 함수, 즉 이고 이라면, 우리는 숫자 에 대한 콜라츠 홀짝성 수열 (또는 홀짝성 벡터)을 로 정의할 수 있다. 여기서 이고, 이다.

어떤 연산이 수행되는지, 즉  또는 는 홀짝성에 따라 달라진다. 홀짝성 수열은 연산 수열과 동일하다.

에 대한 이 형태를 사용하면, 두 숫자 과 의 홀짝성 수열이 처음 항에서 일치하는 것은 과 이 에 대해 합동일 때 그리고 그 때만 가능하다는 것을 보일 수 있다. 이는 모든 숫자가 홀짝성 수열로 고유하게 식별되며, 게다가 여러 우박 순환이 있다면 그에 해당하는 홀짝성 순환은 달라야 한다는 것을 의미한다.

함수 를 숫자 에 번 적용하면 라는 결과가 나온다. 여기서 는  함수를 에 번 적용한 결과이고, 는 그 수열 동안 마주친 증가 횟수이다. 예를 들어, 의 경우 1이 2, 1, 2, 1, 그리고 마지막으로 2로 반복되면서 3번 증가하므로 결과는 가 된다. 의 경우 1이 2로 올라갔다가 1로 떨어지는 동안 1번만 증가하므로 결과는 이 된다. 가 일 때는 번 상승하며 결과는 이 된다. 에 곱해지는 3의 거듭제곱은 의 값과 무관하며, 오직 의 행동에만 의존한다. 이는 특정 형태의 숫자가 일정 횟수의 반복 후 항상 더 작은 숫자로 이어진다는 것을 예측할 수 있게 한다. 예를 들어, 은 를 두 번 적용한 후 이 되고, 은 를 네 번 적용한 후 가 된다. 그러나 이 더 작은 숫자들이 계속해서 1로 이어질지는 의 값에 따라 달라진다.

 태그 체계로서 
단축 형태의 콜라츠 함수에 대해

우박 수열은 생산 규칙이 다음과 같은 2-태그 체계으로 계산할 수 있다.

, , .

이 시스템에서 양의 정수 은  문자의 개 사본으로 구성된 문자열로 표현되며, 태그 연산은 길이가 2 미만인 모든 단어에서 멈춘다. (De Mol에서 발췌.)

콜라츠 추측은 이 태그 시스템이 임의의 유한한  문자열을 초기 단어로 사용하면 결국 멈춘다는 것과 동등하다 (태그 시스템의 작동 예시 참조).

 더 큰 수로의 확장 

 모든 정수에 대한 반복 
콜라츠 추측의 확장은 양의 정수뿐만 아니라 모든 정수를 포함하는 것이다. 밖에서 들어갈 수 없는 0 → 0 주기를 제외하면, 총 네 가지 알려진 주기가 있으며, 모든 0이 아닌 정수는 의 반복 아래에서 결국 이 주기들 중 하나로 들어가는 것으로 보인다. 이 주기들은 아래에 나열되어 있으며, 양의 에 대해 잘 알려진 주기로 시작한다.

홀수 값은 크게 굵은 글씨로 표시되어 있다. 각 주기는 절대값이 가장 작은 (항상 홀수인) 구성원부터 나열된다.

 주기  홀수값 주기 길이  전체 주기 길이 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

일반화된 콜라츠 추측은 모든 정수가 에 의한 반복 아래에서 결국 위 네 가지 주기 중 하나 또는 0 → 0 주기로 들어간다는 주장이다.

 홀수 분모를 가진 유리수에 대한 반복 
콜라츠 맵은 기약분수로 쓰였을 때 홀수 분모를 가지는 (양 또는 음의) 유리수로 확장할 수 있다. 이 숫자는 분자가 홀수인지 짝수인지에 따라 '홀수' 또는 '짝수'로 간주된다. 그러면 지도에 대한 공식은 정의역이 정수일 때와 정확히 동일하다. 여기서 '짝수'인 유리수는 2로 나뉘며, '홀수'인 유리수는 3을 곱하고 1을 더한다. 밀접하게 관련된 사실은 콜라츠 맵이 2-진 정수환으로 확장되며, 이 환은 홀수 분모를 가진 유리수환을 부분환으로 포함한다는 것이다.

콜라츠 맵의 "단축" 정의를 사용할 때, 어떤 주기적인 홀짝성 수열은 정확히 하나의 유리수에 의해 생성된다는 것이 알려져 있다. 반대로, 홀수 분모를 가진 모든 유리수는 결국 주기적인 홀짝성 수열을 가진다고 추측된다 (주기성 추측).

홀짝성 주기가 길이 이고 인덱스 에서 정확히 번 홀수를 포함한다면, 이 홀짝성 주기를 즉시 그리고 주기적으로 생성하는 유일한 유리수는 다음과 같다.

예를 들어, 홀짝성 주기 는 길이가 7이고 인덱스 0, 2, 3, 6에 네 개의 홀수 항을 가진다. 이는 다음 분수로 반복적으로 생성된다.

이는 다음 유리수 순환으로 이어진다.

의 어떤 순환 순열도 위 분수 중 하나와 연관된다. 예를 들어, 순환 은 다음 분수에 의해 생성된다.

일대일 대응을 위해 홀짝성 순환은 기약적이어야 한다. 즉, 동일한 부분 순환으로 분할할 수 없어야 한다. 예를 들어, 홀짝성 순환 과 그 부분 순환 은 최저항으로 줄였을 때 동일한 분수 와 연관된다.

이러한 맥락에서 콜라츠 추측의 타당성을 가정하면, 과 만이 양의 정수 (각각 1과 2)에 의해 생성되는 유일한 홀짝성 순환이라는 의미이다.

만약 유리수의 홀수 분모 가 3의 배수가 아니라면, 모든 반복은 동일한 분모를 가지며, 분자 수열은 콜라츠 함수의 "" 일반화를 적용하여 얻을 수 있다.

 2-진 확장 
함수

는 2-진 정수환 에서 잘 정의되어 있으며, 이 환에서 연속적이고 2-진 측도에 대해 측도 보존적이다. 또한, 그 역학은 에르고딕인 것으로 알려져 있다.

에 작용하는 홀짝성 벡터 함수 를 다음과 같이 정의한다.

함수 는 2-진 등거리변환이다. 결과적으로, 모든 무한 홀짝성 수열은 정확히 하나의 2-진 정수에 대해 발생하며, 따라서 거의 모든 궤적은 에서 비주기적이다.

콜라츠 추측의 동등한 공식화는 다음과 같다.

 실수 또는 복소수에 대한 반복 

콜라츠 맵은 실직선으로 확장될 수 있으며, 가 짝수일 때는 로, 가 홀수일 때는  또는  (단축 버전의 경우)로 평가되는 함수를 선택한다. 이를 보간 함수라고 한다. 간단한 방법은 두 함수 과 를 선택하는 것이다. 여기서

그리고 이들을 원하는 값에 대한 스위치로 사용한다.
.
한 가지 선택은 와 이다. 이 맵의 반복은 동역학계로 이어지며, 이는 마크 챔벌랜드에 의해 further investigation되었다. 그는 이 추측이 양의 실수에 대해 성립하지 않음을 보였다. 이는 무한히 많은 고정점과 무한대로 단조적으로 탈출하는 궤도가 존재하기 때문이다. 함수 는 주기 의 두 개의 끌개 순환을 가진다. 와 . 더욱이, 무한 궤도 집합은 측도 을 가진다고 추측된다.

레더만, 슐라이허, 우드는 연구를 복소평면으로 확장했다. 그들은 복소 사인과 코사인에 대해 챔벌랜드 함수를 사용하고, 추가 항 
를 더했는데, 여기서 는 임의의 전해석 함수이다. 이 표현은 실수 정수에 대해 0으로 평가되므로, 확장된 함수

는 복소평면으로의 콜라츠 맵의 보간이다. 추가 항을 더한 이유는 모든 정수를 의 임계점으로 만들기 위함이다. 이를 통해 그들은 어떤 정수도 베이커 영역에 속하지 않음을 보여주었고, 이는 어떤 정수도 결국 주기적이거나 방황하는 영역에 속한다는 것을 의미한다. 그들은 후자가 사실이 아니라고 추측했으며, 이는 모든 정수 궤도를 유한하게 만들 것이다.


대부분의 점은 무한대로 발산하는 궤적을 가진다. 이 점을 발산 속도에 따라 색칠하면 왼쪽의 이미지가 생성된다(인 경우). 내부의 검은색 영역과 외부 영역은 파투 성분이며, 그들 사이의 경계는 의 쥘리아 집합을 형성하며, 이는 때때로 "콜라츠 프랙탈"이라고 불리는 프랙탈 패턴을 이룬다.


복소 보간 함수를 정의하는 다른 많은 방법이 있는데, 예를 들어 사인과 코사인 대신 복소 지수를 사용하는 것이다.
,
이것은 다른 동역학을 보여준다. 이 경우, 예를 들어 이면, 이다. 오른쪽 그림에 표시된 해당 쥘리아 집합은 셀 수 없이 많은 곡선인 머리카락 또는 광선으로 구성된다.

 최적화 
 시간-공간 상충 관계 
위 홀짝성 수열로서 절에서는 수열 시뮬레이션 속도를 높이는 방법을 제시한다. 각 반복에서  단계를 건너뛰려면 (해당 절의  함수를 사용하여), 현재 숫자를 두 부분으로 나눈다. 하나는  (정수로 해석된 개의 최하위 비트)이며 다른 하나는  (나머지 비트를 정수로)이다.  단계를 건너뛴 결과는 다음과 같다.
.
 (또는 더 나은 )와 의 값은 가능한 모든 -비트 숫자 에 대해 미리 계산할 수 있다. 여기서 는  함수를 에 번 적용한 결과이고, 는 그 과정에서 마주친 홀수의 개수이다. 예를 들어, 인 경우, 숫자의 최하위 5비트를 분리하고 다음을 사용하여 각 반복에서 5단계를 건너뛸 수 있다.

 (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 },
 (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 }.

이것은 결과 계산 속도를 배 높이기 위해 의 선행 계산과 저장을 필요로 하는데, 이는 시간-공간 상충 관계이다.

 모듈러 제약 
콜라츠 추측에 대한 반례를 찾는 특별한 목적을 위해, 이 선행 계산은 토마스 올리베이라 에 실바가 큰  값까지 콜라츠 추측의 계산적 확인에서 사용한 훨씬 더 중요한 가속을 가져온다. 만약 주어진 와 에 대해 다음 부등식

이 모든 에 대해 성립한다면, 첫 번째 반례가 존재하더라도 그것은 를 법으로 하는 가 될 수 없다. 예를 들어, 첫 번째 반례는 홀수여야 한다. 왜냐하면 은 보다 작기 때문이다. 그리고 4를 법으로 하여 3이어야 한다. 왜냐하면 은 보다 작기 때문이다. 콜라츠 추측의 반례가 아닌 각 시작 값 에 대해, 그러한 부등식이 성립하는 가 존재하므로, 하나의 시작 값에 대해 콜라츠 추측을 확인하는 것은 전체 합동류를 확인하는 것과 같다. 가 증가함에 따라, 검색은 더 낮은  값에 의해 제거되지 않는 나머지 만 확인하면 된다. 지수적으로 작은 비율의 나머지들만이 살아남는다. 예를 들어, 모듈로 32에서 살아남는 나머지는 7, 15, 27, 31뿐이다.

3으로 나누어 떨어지는 정수는 순환을 형성할 수 없으므로, 이러한 정수는 반례로 확인할 필요가 없다.

 시러큐스 함수 
가 홀수 정수이면, 은 짝수이므로, 이고 은 홀수이며 이다. 시러큐스 함수는 양의 홀수 정수 집합 에서 자기 자신으로 가는 함수 이며, 이다. 

시러큐스 함수의 일부 속성은 다음과 같다.

 모든 에 대해, . (왜냐하면 이기 때문이다.)
 더 일반적으로: 모든  및 홀수 에 대해, . (여기서 은 함수 반복 표기법이다.)
 모든 홀수 에 대해, 

콜라츠 추측은 의 모든 에 대해, 인 정수 이 존재한다는 진술과 동등하다.

 미결정 일반화 
1972년, 존 호턴 콘웨이는 콜라츠 문제의 자연스러운 일반화가 알고리즘적으로 미결정임을 증명했다.

구체적으로, 그는 다음 형태의 함수를 고려했다.

여기서 은 이 항상 정수가 되도록 선택된 유리수이다. 표준 콜라츠 함수는 , , , , 로 주어진다. 콘웨이는 문제

 주어진 와 에 대해 반복 수열 이 에 도달하는가?

가 이 방식으로 정지 문제를 나타냄으로써 미결정임을 증명했다.

콜라츠 문제에 더 가까운 것은 다음의 전칭 양화된 문제이다.

 주어진 에 대해, 반복 수열 이 모든 에 대해 에 도달하는가?

이러한 방식으로 조건을 수정하면 문제가 해결하기 더 어려워지거나 쉬워질 수 있다(직관적으로, 긍정적인 답변을 정당화하기는 더 어렵지만 부정적인 답변을 정당화하기는 더 쉬울 수 있다). 커츠와 사이먼 As PDF은 전칭 양화된 문제가 실제로 미결정이며 산술적 위계에서 더 높다는 것을 증명했다. 특히, 이는 -완전이다. 이 난이도 결과는 함수 의 클래스를 법 를 6480으로 고정하여 제한하더라도 유효하다.

모든 가 0인 이 형태의 간략화된 버전에서 의 반복은 FRACTRAN이라는 난해한 프로그래밍 언어로 정형화된다.

 계산 복잡도 
콜라츠 및 관련 추측은 종종 계산 복잡도를 연구할 때 사용된다. 연결은 바쁜 비버 함수를 통해 이루어지는데, 여기서 BB(n)은 정지하는 모든 n 상태 튜링 기계가 취하는 최대 단계 수이다. 콜라츠 추측과 밀접하게 관련된 에르되시 팔의 추측이 거짓일 경우에만 정지하는 15 상태 튜링 기계가 있다. 따라서 BB(15)가 알려져 있고, 이 기계가 그 단계 수 내에서 멈추지 않았다면, 그것은 영원히 실행될 것이고 따라서 반례가 존재하지 않는다는 것이 알려지게 된다 (이는 추측이 참임을 증명한다). 이것은 추측을 해결하는 데 완전히 비실용적인 방법이다. 대신, BB(15)를 계산하는 것이 적어도 이 콜라츠와 유사한 추측을 해결하는 것만큼 어렵다는 것을 시사하는 데 사용된다.

 같이 보기 
  반군
 산술 동역학
 저글러 수열
 모듈러 산술
 나머지류별 아핀 군

 내용주 

 각주 

 외부 링크 


 데이비드 바르지나의 진행 중인 자원 봉사 컴퓨팅 프로젝트 는 큰 값에 대한 콜라츠 추측의 수렴을 검증한다. (현재까지 가장 큰 진척)
 (BOINC) 자원 봉사 컴퓨팅 프로젝트 는 더 큰 값에 대한 콜라츠 추측을 검증한다.
 에릭 루센달의 진행 중인 자원 봉사 컴퓨팅 프로젝트는 점점 더 큰 값에 대한 콜라츠 추측을 검증한다.
 토마스 올리베이라 에 실바의 또 다른 진행 중인 자원 봉사 컴퓨팅 프로젝트는 콜라츠 추측을 계속 검증한다 (에릭 루센달의 페이지보다 통계는 적지만 더 큰 진척을 보임).






 컴퓨터가 이 악명 높은 다루기 힘든 수학 문제를 풀 준비가 되었는가?

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