콜라츠 추측

콜라츠 지도에서 짝수를 건너뛰고 작은 숫자의 궤도를 보여주는 방향 그래프입니다.Collatz 추측은 모든 경로가 결국 1로 이어진다는 것을 나타냅니다.

콜라츠 추측은 수학에서 가장 유명한 미해결 문제 중 하나이다.추측은 두 개의 간단한 산술 연산을 반복하는 것이 결국 모든 양의 정수를 1로 변환할지 여부를 묻습니다.각 항이 이전 항에서 얻은 정수 수열과 관련된다. 이전 항이 짝수이면 다음 항은 이전 항의 절반이다.이전 항이 홀수일 경우 다음 항은 이전 항에 3을 곱하고 1을 더한 값입니다.추측에 의하면, 이러한 시퀀스는, 시퀀스를 개시하기 위해서 어떤 양의 정수가 선택되든, 항상 1에 도달합니다.

이는 박사학위를 ^[1]받은 지 2년 만인 1937년 이 아이디어를 도입한 수학자 로타 콜라츠의 이름을 딴 것이다.3n+1 문제, 3n+1 추측, 울람 추측(스타니스와프 울람 이후), 카쿠타니 문제(시즈오 카쿠타니 이후), 스웨이파 추측(브라이언 스웨이츠 이후), 하세 알고리즘(헬무트 하세 이후), 시라쿠사 ^[2][4]문제라고도 한다.관련된 숫자의 시퀀스는 우박 시퀀스, 우박 번호 또는 우박 숫자(보통 값이 ^[5][6]구름의 우박과 같은 여러 강하 및 상승에 영향을 받기 때문에) 또는 경이로운 ^[7]숫자로도 불린다.

폴 에르데스는 콜라츠 추측에 대해 "수학은 그러한 문제에 ^[8]대해 준비가 되어 있지 않을 수 있다"고 말했다.그는 또한 ^[9]이 솔루션을 위해 미화 500달러를 제시했습니다.제프리 라가리아스는 2010년에 콜라츠 추측은 "현재의 ^[10]수학이 전혀 미치지 못하는 매우 어려운 문제"라고 말했다.

문제의 기술

1~9999 의 수치와 대응하는 합계 정지 시간

숫자 1 ~ 10의⁸ 총 정지 시간 히스토그램입니다.총 정지 시간은 x축에 있고 주파수는 y축에 있습니다.

숫자 1 ~ 10의⁹ 총 정지 시간 히스토그램입니다.총 정지 시간은 x축에 있고 주파수는 y축에 있습니다.

2 ~ 10의⁷ 입력에 대한 반복 시간입니다.

최대 250, 1000, 4000, 20000, 100000, 500000까지의 합계 정지 시간

임의의 양의 정수에 대해 다음 연산을 고려합니다.

• 짝수면 2로 나누세요.
• 만약 숫자가 홀수라면, 그것을 세 배로 해서 하나를 더하세요.

모듈식 산술 표기법에서는 함수 f를 다음과 같이 정의합니다.

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

이제 이 작업을 임의의 양의 정수부터 시작하여 각 단계의 결과를 다음 입력으로 반복하여 시퀀스를 형성합니다.

표기법:

$$({displaystyle a_{i}=cases}n&{\text{cases}n&{\f(a_{i-1})&{\text{i}i>0\end{cases}}})$$

콜라츠 추측은 다음과 같습니다.이 프로세스는 처음에 어떤 양의 정수가 선택되었는지에 관계없이 최종적으로 숫자 1에 도달합니다.

추측이 거짓일 경우, 이는 1을 포함하지 않는 시퀀스를 발생시키는 시작 번호가 있기 때문일 수 있습니다.이러한 시퀀스는 1을 제외한 반복 사이클에 들어가거나 제한 없이 증가합니다.이러한 시퀀스는 발견되지 않았습니다.

a₀ < a가 n의 정지시간이라고 불릴 정도로_i 가장 작은i를 가리킵니다.마찬가지로, a = 1이 될 정도로_k 가장 작은 k를 ^[3]n의 총 정지 시간이라고 합니다.인덱스 i 또는 k 중 하나가 존재하지 않으면 각각 정지시간 또는 총 정지시간이 무한하다고 합니다.

콜라츠 추측은 모든 n개의 총 정지 시간이 유한하다고 주장한다.이것은 또한 모든 n ÷ 2의 정지시간이 유한하다는 것과 같다.

3n + 1은 n이 홀수일 때마다 짝수이므로 대신 콜라츠 함수의 "바로 가기" 형식을 사용할 수 있습니다.

$${\displaystyle f(n)=flac {n}{2}}&{\text{if}}n\equiv 0pmod {2},\[4px]{\frac {3n+1}{2}}}&{\text{if}}n\equiv 1gpmod {2}.\end {case}}$$

경험적 데이터

예를 들어, n = 12에서 시작하여 함수 f를 "f" 없이 적용하면 12, 6, 3, 10, 5, 16, 8, 4, 2, 1을 얻을 수 있다.

숫자 n = 19는 1:19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1에 도달하는 데 더 오래 걸립니다.

아래에 나열되고 그래프로 표시된 n = 27의 순서는 111단계(굵은 글씨로 홀수까지 41단계)로, 1로 내리기 전에 9232까지 올라간다.

27, 82, 41, 124, 62, 94, 47, 142, 71, 214, 107, 322, 161, 482, 121, 364, 182, 91, 274, 137, 412, 206, 103, 3105, 466, 233, 700, 175, 526, 263, 790, 395, 593, 17890, 8801822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 160, 80, 16, 20, 16, 20, 20, 16, 16, 16, 16, 16, 16, 16, 20

총 정지 시간이 더 작은 시작 값보다 긴 숫자는 다음부터 시작하는 시퀀스를 형성합니다.

1, 2, 3, 6, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171, ...(OEIS의 시퀀스 A006877).

최대 궤적 지점이 더 작은 출발 값보다 큰 출발 값은 다음과 같다.

1, 2, 3, 7, 27, 255, 447, 639, 703, 1819, 425, 4591, 9663, 20895, 26623, 31911, 60975, 77671, 113383, 138367, 159487, 270271, 665215, 704511, ... (시퀀스 A006884E)

n이 1에 도달하기 위한 스텝의 수는 다음과 같습니다.

0, 1, 7, 2, 8, 16, 3, 19, 6, 14, 9, 17, 17, 4, 20, 7, 15, 15, 10, 23, 10, 111, 18, 18, 18, 18, 18, 106, 26, 13, 13, 21, 21, 34, 8, 109, 29, 24, 16, 16, 16, 16, 16, 24, 16, 16, 16, 16, 16, 16, 16, 16, 15, 15, 16, 15, 15, 23, 23, 16, 16, 16, 16, 16, 17, 20, 20, 17, 17, 18, 18, 18, 18, 18, 18, 18, 15

총 정지 시간이 최대인 시작 값

10보다 작으면 9이고, 19개의 스텝이 있습니다.

100보다 작으면 97이고, 118개의 스텝이 있고

less 1000은 871로 178개의 스텝이 있습니다.

10보다⁴ 작으면 6171이고, 261개의 스텝이 있습니다.

10보다⁵ 작으면 77031로 350개의 스텝이 있습니다.

10보다⁶ 작으면 837799로 524개의 스텝이 있습니다.

10보다⁷ 작으면 8400511로 685개의 스텝이 있습니다.

10보다⁸ 작으면 63728127로 949개의 스텝이 있습니다.

10 미만이면⁹ 670617279로 986개의 스텝이 있습니다.

10보다¹⁰ 작으면 9780657630으로 1132개의 ^[11]스텝이 있습니다.

10보다¹¹ 작으면 75128138247로 1228개의 스텝이 있습니다.

10보다¹² 작으면 989345275647로 1348개의 ^[12]스텝이 있습니다.

이들 수치는 스텝카운트가 표시된 가장 낮은 수치이지만 반드시 지정된 제한보다 낮은 수치일 필요는 없습니다.예를 들어 9780657631에는 1132개의 스텝이 있고 9780657630에도 1132개의 스텝이 있습니다.

2가 n배로 반감되어 1이 되기 때문에ⁿ 2의 합계 정지시간이 최소인 시작값은 2의 거듭제곱이 됩니다.

시각화

• 

  처음 1000개 숫자의 궤도를 나타내는 방향 그래프입니다.

• 

  x축은 시작 수를 나타내고 y축은 체인에서 1에 도달한 가장 높은 수를 나타냅니다.이 그림은 제한된 y축을 보여줍니다. 일부 x 값은 2.7×10⁷(x = 9663의 경우)의 중간값을 생성합니다.

• 

  스텝이 20 미만인 모든 숫자의 트리.

• 

  첫 번째 1억 개에 대해 1번까지 반복하는 횟수입니다.

뒷받침하는 인수

비록 그 추측이 입증되지는 않았지만, 그 문제를 조사한 대부분의 수학자들은 실험적인 증거와 발견적 주장이 그것을 뒷받침하기 때문에 그 추측이 사실이라고 생각한다.

실험 증거

2020년 현재^[update], 이 추측은 2⁄ 2.95×10까지의⁶⁸²⁰ 모든 시작 값에 대해 컴퓨터로 확인되었습니다.지금까지 테스트된 모든 초기값은 결국 주기 ^[13]3의 반복 주기(4; 2; 1)로 종료됩니다.

이 컴퓨터 증거는 모든 시작 값에 대해 추측이 참이라는 것을 증명하기에 충분하지 않다.폴랴 추측과 같이 일부 반증된 추측의 경우처럼, 매우 큰 숫자를 고려할 때 반례를 찾을 수 있다.

그러나 이러한 검증은 다른 영향을 미칠 수 있다.예를 들어, 사소하지 않은 ^[14][15][16]순환의 주기 및 구조 형태에 대한 추가 제약을 도출할 수 있다.

확률론적 휴리스틱

Collatz 프로세스에 의해 생성된 시퀀스의 홀수만 고려한다면 각 홀수는 평균입니다.앞의 ^[17]4분의 3입니다.(정확히 말하면 결과 비율의 기하 평균은 3/4입니다.)이것은 모든 헤일스톤 시퀀스가 장기적으로 감소해야 한다는 휴리스틱한 주장을 낳는다. 비록 이것이 다른 주기에 대한 증거는 아니지만, 오직 발산에만 대한 증거이다.이 주장은 Hailstone 시퀀스가 상관없는 확률론적 사건으로부터 조립된다고 가정하기 때문에 증거는 아니다. (이것은 Collatz 프로세스의 2-adic 확장이 거의 모든 2-adic 시작 값에 대한 모든 곱셈 단계에 대해 두 개의 분할 단계를 갖는다는 것을 엄격하게 확립한다.)

정지 시간

Riho Teras에 의해 증명되었듯이, 거의 모든 양의 정수는 제한된 정지 시간을 ^[18]가지고 있습니다.즉, 거의 모든 Collatz 시퀀스는 초기값보다 완전히 낮은 지점에 도달합니다.증명은 패리티 벡터의 분포를 기반으로 하며 중심 한계 정리를 사용합니다.

2019년 테렌스 타오는 로그 밀도를 사용하여 이 함수가 아무리 느리게라도 무한대로 분산될 경우 거의 모든 콜라츠 궤도가 시작점의 주어진 함수 아래로 하강한다는 것을 보여줌으로써 이 결과를 개선했다.이 연구에 대해, Quanta Magazine은 Tao가 "수십 ^[19][20]년 만에 콜라츠 추측에 대한 가장 중요한 결과 중 하나를 얻어냈다"고 썼다.

하한

컴퓨터 지원 증명에서, 크라시코프와 라가리아스는 결국 1에 도달하는 구간의 정수 수가 충분히 큰 모든 x에 대해 최소한 ^[21]x와 같다는 것을 보여주었다^0.84.

사이클

이 부분에서는 Collatz 함수의 바로 가기 형식을 고려합니다.

$${\displaystyle f(n)=flac {n}{2}}&{\text{if}}n\equiv 0pmod {2},\[4px]{\frac {3n+1}{2}}}&{\text{if}}n\equiv 1gpmod {2}.\end {case}}$$

유일하게 알려진 사이클은 주기 2의 (1,2)로, 트리벨 사이클이라고 불립니다.

사이클 길이

사소한 주기가 아닌 주기의 길이는 적어도 17087915인 ^[15]것으로 알려져 있다.사실, Eliahou(1993)는 모든 비사소한 순환의 주기 p가 다음과 같은 형태라는 것을 증명했다.

$${\displaystyle p=301994a+17087915b+85137581c}$$

최근 2까지⁶⁸ 추측의 검증을 설명하는 유사한 추론은 개선된 하한 114208327604(또는 "바로 가기"가 없는 1862657595)로 이어진다.이 하한은 114208327604 = 17087915 × 361 + 85137581 × 1269이므로 위의 결과와 일치한다.

k사이클

k 사이클은 2k의 연속된 연속된 연속으로 분할할 수 있는 사이클이다. 즉, k는 홀수 시퀀스를 증가시키고 k는 짝수 ^[16]시퀀스를 감소시킨다.예를 들어, 사이클이 홀수의 단일 증가 시퀀스와 짝수의 감소 시퀀스로 구성되어 있는 경우, 이를 1-사이클이라고 합니다.

Steiner(1977)는 사소한 (1;^[22] 2) 외에 1-주기가 없다는 것을 증명했다.Simons(2005)는 2사이클이 ^[23]없음을 증명하기 위해 Steiner의 방법을 사용했다.Simons & de Weger(2005)는 이 증명을 최대 68 사이클까지 확장했습니다. k =^[16] 68까지는 k 사이클이 없습니다.이 방법은 68을 초과하는 각 k에 대해 k-사이클의 최소 항에 대한 상한을 제공한다. 예를 들어 77-사이클이 있는 경우 사이클의 최소 1개의 요소는 38137×2^{50 [16]}미만이다.2까지의⁶⁸ 추측의 검증과 함께, 이는 k = ^[13]77까지의 비결정 k-사이클이 존재하지 않음을 의미한다.철저한 컴퓨터 검색이 계속됨에 따라 더 큰 k 값은 제외될 수 있습니다.좀 더 직관적으로 설명하자면, 최대 77개의 회선을 가진 사이클을 찾을 필요는 없습니다.각 회선은 연속적인 업과 연속적인 다운으로 구성됩니다.

추측의 다른 공식화

역방향으로

콜라츠 그래프의 처음 21단계는 상향식으로 생성되었습니다.그래프는 궤도 길이가 21 이하인 모든 숫자를 포함합니다.

추측을 입증하는 또 다른 접근법이 있는데, 그것은 소위 콜라츠 그래프를 성장시키는 상향식 방법을 고려한다.콜라츠 그래프는 역관계에 의해 정의된 그래프입니다.

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

따라서, 모든 양의 정수가 결국 1로 이어진다는 것을 증명하는 대신, 우리는 1이 모든 양의 정수로 거꾸로 이어진다는 것을 증명하려고 시도할 수 있습니다.임의의 정수 n에 대해 3n + 1 4 4(mod 6)의 경우에만 n 1 1(mod 2)입니다.마찬가지로 n 4 4(mod 6)인 경우에만 n - 1/3 ( 1(mod 2)이 됩니다.추측적으로 이 역관계는 1-2-4 루프(이 문서의 문제 설명 섹션에 정의된 변경되지 않은 함수 f의 4-2-1 루프 역)를 제외하고 트리를 형성한다.

함수 f의 관계 3n + 1을 공통 대체 "바로 가기" 관계 3n + 1/2로 바꾸면, 콜라츠 그래프는 역관계로 정의된다.

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

임의의 정수 n에 대해 3n + 1/2 2 2(mod 3)일 경우에만 n 1 1(mod 2)입니다.마찬가지로 n - 2(mod 3)일 경우에만 2n - 1/3 1 1(mod 2)이 됩니다.추측적으로 이 역관계는 1-2 루프를 제외하고 트리를 형성한다(위에서 설명한 것처럼 수정된 함수 f(n)의 1-2 루프의 역).

또는 3n + 1을 nµ/H(nµ)로 바꿉니다. 여기서 nµ = 3n + 1이고 H(nµ)는 nµ를 나누는 2의 최대 제곱입니다(나머지 없음).결과 함수 f는 홀수에서 홀수로 매핑됩니다.이제 어떤 홀수 n의 경우 이 연산을 k회 적용하면 숫자 1(즉, f^k(n) = 1)이 나온다고 가정합니다.다음으로 이진법에서 숫자 n은 문자열_k w_k−1... w의₁ 결합으로 쓸 수 있습니다.여기서_h 각 w는 1/3의^{h [24]}표현에서 유한하고 연속적인 추출물입니다.따라서 n의 표현은 1/3의^h 반복을 유지합니다.여기서 각 반복은 임의로 회전하여 한정된 비트수까지 복제됩니다.이것은 바이너리에서만 발생합니다.^[25]추측컨대, '1'로 끝나는 모든 이진 문자열은 이 형식의 표현으로 도달할 수 있습니다(여기서는 선행하는 '0'을 s에 추가하거나 삭제할 수 있습니다).

기본 2에서 계산하는 추상 기계로서

콜라츠 함수의 반복 적용은 비트 문자열을 처리하는 추상 기계로 표현될 수 있습니다.기계는 홀수 번호에 대해 다음 세 단계를 수행합니다.1이 남았습니다.

1. 2진수(2n + 1)의 숫자의 오른쪽 끝에 1을 추가합니다.
2. 이 값을 이진수 덧셈으로 원래 숫자에 추가합니다(2n + 1 + n = 3n + 1).
3. 모든 후행 0을 제거합니다(즉, 결과가 홀수일 때까지 반복하여 2로 나눕니다).

예

시작 숫자 7은 2번 밑부분에 111로 쓰여 있다.결과 Collatz 시퀀스는 다음과 같습니다.

111 1111 1011010111 1000111 110100 1101000 1011 10000

패리티 시퀀스로서

이 섹션에서는 약간 변경된 형식의 Collatz 함수를 검토합니다.

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

이것은 n이 홀수일 때 3n + 1이 항상 짝수이기 때문에 가능합니다.

P(...)가 숫자의 패리티인 경우, 즉 P(2n) = 0 및 P(2n + 1) = 1이면 숫자 n에 대한 Collatz 패리티 시퀀스(또는 패리티 벡터)를 p = P(a_i) 및 a = f₀(a_i)로_ii+1 정의할 수 있습니다.

3n + 1/2 또는 n/2 중 어떤 동작이 수행될지는 패리티에 따라 달라집니다.패리티 시퀀스는 동작 시퀀스와 동일합니다.

f(n)에 대해 이 형식을 사용하면 m과 n이 동등한 모듈로^k 2인 경우에만 두 숫자 m과 n의 패리티 시퀀스가 첫 번째 k 항에서 일치함을 알 수 있습니다.이는 모든 번호가 패리티 시퀀스에 의해 고유하게 식별되며, 또한 여러 Hailstone 사이클이 있는 경우 대응하는 패리티 사이클이 ^[3][18]달라야 함을 의미합니다.

숫자 n = 2a^k + b에 f 함수 k를 적용하면 결과 3a^c + d가 된다. 여기서 d는 f 함수를 b에 k번 적용한 결과이고 c는 해당 시퀀스 동안 발생한 증가 횟수이다.예를 들어, 2a⁵ + 1의 경우 1이 2, 1, 2, 마지막으로 2로 반복될 때 3이 증가하므로 3a³ + 2가 되고, 2a² + 1의 경우 1이 상승하여 1이 되므로 3a + 1이 됩니다.b가^k 2 - 1일 때 k가 상승하고 결과는 2 × 3a^k - 1이 됩니다.3 곱하기 a의 계수는 a의 값과 독립적이며 b의 동작에만 의존합니다.이를 통해 특정 형태의 숫자가 일정 횟수 반복된 후에는 항상 더 적은 수로 이어질 것임을 예측할 수 있습니다. 예를 들어, 4a + 1은 f의 두 적용 후 3a + 1이 되고 16a + 3은 f의 4 적용 후 9a + 2가 됩니다.그러나 이러한 작은 숫자가 1로 계속되는지 여부는 a의 값에 따라 달라집니다.

태그 시스템으로서

폼의 콜라츠 함수의 경우

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

Hailstone 시퀀스는 생산 규칙을 사용하여 매우 단순한 2-태그 시스템으로 계산할 수 있습니다.

a → bc, b → a, c → aaa.

이 시스템에서 정의 정수 n은 a의 n개의 복사본 문자열로 나타나며, 태그 연산의 반복은 2보다 작은 단어로 정지한다(De Mol에서 채택).

Collatz 추측은 의 임의의 유한 문자열을 선두 워드로 하여 이 태그 시스템이 최종적으로 정지하는 것을 동등하게 나타내고 있습니다(태그 시스템 번호 참조).예: 작업 예제의 Collatz 시퀀스 계산).

더 큰 도메인에 대한 확장

모든 정수에 대해 반복

콜라츠 추측의 확장은 양의 정수뿐만 아니라 모든 정수를 포함하는 것입니다.외부에서 입력할 수 없는 사이클 0 → 0을 제외하고, 알려진 사이클은 총 4개이며, 0이 아닌 모든 정수는 결국 f의 반복 하에 들어가는 것으로 보입니다.다음은 양의 n에 대한 잘 알려진 사이클부터 시작하는 사이클 목록입니다.

홀수 값은 굵은 글씨로 표시됩니다.각 사이클은 가장 낮은 절대값(항상 홀수)의 멤버와 함께 먼저 나열됩니다.

일반화 콜라츠 추측은 f에 의해 반복되는 모든 정수는 결국 위의 4개의 사이클 또는 0 → 0 중 하나에 속한다는 주장이다. (0 → 0 사이클은 완전성을 위해서만 포함된다.)

홀수 분모를 가진 이성들을 반복한다.

콜라츠 맵은 가장 낮은 항으로 쓸 때 홀수 분모를 갖는 (양수 또는 음수) 유리수로 확장할 수 있습니다.이 숫자는 분자가 홀수인지 짝수인지에 따라 '홀수' 또는 '짝수'로 간주됩니다.그러면 지도의 공식은 도메인이 정수일 때와 정확히 같다: "짝수" 그런 유리성을 2로 나누고, "홀수" 그런 유리성을 3으로 곱한 다음 1을 더한다.콜라츠 맵은 홀수 분모를 서브링으로 하는 유리 고리를 포함하는 2-adic 정수의 링까지 확장됩니다.

Collatz 맵의 "바로 가기" 정의를 사용할 경우, 모든 주기적 패리티 시퀀스는 정확히 하나의 ^[26]이성에 의해 생성되는 것으로 알려져 있습니다.반대로, 홀수 분모를 가진 모든 유리에는 결국 순환 패리티 시퀀스가 있다고 추측됩니다(주기성 추측^[3]).

패리티 사이클의 길이가 n이고 k₀ < < < k에서_m−1 정확히 m배의 홀수를 포함하는 경우 이 패리티 사이클을 즉시 정기적으로 생성하는 고유한 유리성은 다음과 같습니다.

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

(1)

예를 들어, 패리티 사이클(1 0 1 0 1)의 길이는 7이고 인덱스 0, 2, 3, 6에 4개의 홀수 항이 있습니다.분수에 의해 반복적으로 생성됩니다.

$${{displaystyle {3^{3}2^{2}2^{2}+3^{1}2^{3}+3^{0}2^{6}}{2^{7}-3^{4}}=black{47}}}$$

$$(*displaystyle\frac{47}\rightarrow{frac{250}{47}\rightarrow{frac{211}{47}\rightarrow{frac{170}{47}\rightarrow{f}{frac}{47}\rightarrow{f}\frightarrow{f}{f}{f}{f}{f}{frightarrow}{f}\frightarrow}}$$

(1 0 1 1 0 0 1)의 주기적 순열은 위의 분수 중 하나와 관련이 있습니다.예를 들어, 주기(0 1 1 0 0 1 1)는 다음 분수에 의해 생성됩니다.

$$({displaystyle {3^{3}2^{1}+3^{2}2^{2}+3^{1}2^{5}+3^{0}2^{6}}}{2^{7}-3^{4}}=250}{47}).}$$

일대일 대응의 경우 패리티 사이클은 축소할 수 없습니다.즉, 동일한 서브 사이클로 분할할 수 없습니다.예를 들어 패리티 사이클(1 1 0 0 1 0 0)과 그 서브 사이클(1 1 0 0 0)은 가장 낮은 항으로 감소했을 때 동일한 분수 5/7에 관련지어집니다.

이 맥락에서 콜라츠 추측의 타당성을 가정하는 것은 (1 0)과 (0 1)이 양의 정수(1 및 2)에 의해 생성되는 유일한 패리티 사이클임을 의미합니다.

만약 어떤 이성의 홀수분모 d가 3의 배수가 아니라면, 모든 반복은 같은 분모를 가지며 분자의 시퀀스는 콜라츠 함수의 "3n + d"를 적용하여^[27] 얻을 수 있다.

$${\displaystyle T_{d}(x)=begin{case}{\text{if}}}x\equiv 04pmod {2},\\[4px]{\frac {3x+d}{2}}}&{\text{if}}x\equiv 1gpmod {2}.\end {case}}$$

2-adic 확장

함수

$$\displaystyle T(x)=begin{case}{\frac {x}{2}&{\text{if}}x\equiv 04pmod {2}\\[4px]{\frac {3x+1}{2}}}&{\text{if}}x\equiv 1gpmod {2}}\end{case}}$$

는 2-adic 정수의 $링{\displaystyle {\mathbb{}}_{}}$ $(\$${2})$에 잘 정의되어 있으며, 2-adic 측정과 관련하여 연속적이고 측정이 유지됩니다.게다가, 그것의 역동성은 ^[3]에르고딕한 것으로 알려져 있다.

$Z$ 2$(\$displaystyle $\mathbb {Z} _{2})$에 작용하는 패리티 벡터 함수 Q를 다음과 같이 정의합니다.

$${\displaystyle Q(x)=\sum _{k=0}^{\infty}\left(T^{k}(x)\mod 2\right)2^{k}.}$$

함수 Q는 2-adic Isometry입니다.^[28]따라서 모든 무한 패리티 시퀀스는 정확히 하나의 2-adic 정수에 대해 발생하므로 거의 모든 궤적이 Z $(\$에서 비순환적입니다.

콜라츠 추측의 등가 공식은 다음과 같다.

$${\displaystyle Q\left(\mathbb {Z} ^{+}\right)\subset {tfrac {1}{3}}\mathbb {Z}.}$$

실수 또는 복소수 반복

Collatz 지도의 실제 확장에 있어서의 궤도 10-5-8-4-2-1-2-1-1-등의 거미줄 그림(「3n+1」을 「3n+1)/2」로 대체해 최적화)

콜라츠 맵(숏컷 포함)은 스무스 맵의 정수에 대한 제한으로 볼 수 있습니다.

$$({displaystyle f(z)=frac {1}{2}\cos ^{2}\left\frac {pi }{2})+{\frac {3z+1}{2}\sin ^{2}\frac {{pi }{2}}z\right}).}$$

실제 라인 부근의 콜라츠 맵 프랙탈

이 지도를 실제 선상에서 반복하면 동적 시스템이 생성되어 챔버랜드에 ^[29]의해 더 자세히 조사됩니다.그는 단조롭게 무한대로 빠져나가는 궤도와 무한대로 고정된 점들이 무한히 많기 때문에 이 추측은 양의 실수에 해당하지 않는다는 것을 보여주었다.함수 f는 주기 2의 두 개의 유인 사이클, (1; 2) 및 (1.1925...)를 가집니다.; 2.1386...)또한 무한궤도의 집합은 측정값 0으로 추측된다.

Letherman, Schleicher 및 Wood는 연구를 복잡한 평면으로 확장했으며, 여기서 대부분의 점들은 무한대로 갈라지는 궤도를 가지고 있다(^[30]그림의 색상 영역).유색 영역과 검은색 성분 사이의 경계, 즉 f의 줄리아 집합은 "콜라츠 프랙탈"이라고 불리는 프랙탈 패턴입니다.

최적화

시공간 트레이드오프

위의 '패리티 시퀀스' 섹션에서는 시퀀스의 시뮬레이션을 가속화하는 방법을 제공합니다.(그 섹션의 f 함수를 사용하여) 각 반복에서 k개의 스텝을 건너뛰려면 현재 번호를 b(정수로 해석되는 k개의 최하위 비트)와 a(나머지 비트의 정수)의 두 부분으로 나눕니다.k 스텝 앞으로 점프한 결과는 다음과 같다.

f^k(2a^k + b) = 3a^c(b) + d(b).

c(또는 보다 나은^c 3) 및 d 배열은 가능한 모든 k비트 번호 b에 대해 사전 계산됩니다.d(b)는 f 함수를 b에 k회 적용한 결과이고 c(b)는 ^[31]도중에 발견된 홀수 수입니다.예를 들어, k = 5일 경우, 숫자의 최하위 비트 5개를 분리하고 다음을 사용하여 각 반복에서 5단계씩 앞으로 점프할 수 있습니다.

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

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

이를 위해서는 2개의 사전 컴퓨팅과 스토리지가 있어야^k 시공간 트레이드오프인 k배만큼 계산 속도를 높일 수 있습니다.

모듈러 제한

콜라츠 추측에 대한 반례를 찾는 특별한 목적을 위해, 이 사전 연산은 토마스 올리베이라 에 실바가 콜라츠 추측의 계산 확인에서 n의 큰 값까지 사용하는 훨씬 더 중요한 가속으로 이어진다. 만약, 주어진 b와 k에 대해, 부등식이 있다면,

f^k(2a^k + b) = 3a^c(b) + d(b) < 2a^k + b

모든 a에 대해 유지되며, 첫 번째 반례가 존재할 경우 bodulo^{k [14]}2가 될 수 없습니다.예를 들어, 첫 번째 반례는 f(2n) = n으로 2n보다 작기 때문에 홀수여야 하며, f(4n + 1) = 3n + 1로 4n + 1보다 작기 때문에² 3mod 4여야 합니다.Collatz 추측의 반례가 아닌 각 시작값 a에 대해 이러한 부등식이 유지되는 k가 있으므로 하나의 시작값에 대해 Collatz 추측을 확인하는 것은 전체 일치 클래스를 확인하는 것과 같다.k가 증가하면 검색에서는 k의 낮은 값으로 제거되지 않는 잔류물 b만 검사하면 됩니다.잔류물의 기하급수적으로 적은 부분만이 ^[32]살아남는다.예를 들어 잔류물 mod 32는 7, 15, 27 및 31뿐입니다.

시러큐스 함수

k가 홀수 정수일 경우 3k + 1은 짝수이므로 k and 홀수일 경우 3k + 1 = 2kµ이고^a 1 1이다.시러큐스 함수는 홀수 정수 집합 I에서 f(k) = kµ(OEIS의 시퀀스 A075677)인 함수 f이다.

시러큐스 함수의 속성은 다음과 같습니다.

• 모든 k µ I에 대해 f(4k + 1) = f(k)입니다(3k + 1) + 1 = 12k + 4 = 4(3k + 1)입니다).
• 일반성 향상:모든 p ≤ 1 및 홀수 h에 대해^{p − 1} f(2h^p - 1) = 2 × 3h^{p − 1} - 1. (여기서^{p − 1} f는 함수 반복 표기법입니다.)
• 모든 홀수 h에 대해 f(2h - 1) 3 3h - 1/2

콜라츠 추측은 I의 모든 k에 대해 f(k) = 1인ⁿ 정수 n ≤ 1이 존재한다는 진술과 같다.

결론을 내릴 수 없는 일반화

1972년, John Horton Conway는 Collatz 문제의 자연적 일반화는 알고리즘적으로 결정할 ^[33]수 없다는 것을 증명했다.

구체적으로, 그는 형태의 기능을 고려했다.

$${\displaystyle {g(n)=a_{i}n+b_{i}}\;,{\text{where}}\;{n\equiv ipmod {P}}}}$$

표준₀ 콜라츠 함수는 P = 2, a = 1/2, b₀ = 0, a₁₁ = 3, b = 1로 제공됩니다. Conway는 문제가 다음과 같이 증명되었습니다.

g와 n을 지정하면 g(n)의^k 반복 시퀀스가 1에 도달합니까?

정지하는 문제를 이렇게 표현함으로써 판별할 수 없습니다.

Collatz 문제에 더 가까운 것은 다음과 같은 보편적으로 수량화된 문제입니다.

g를 지정하면 g(n)의^k 반복 시퀀스는 모두n > 0에 대해1에 도달합니까?

이러한 방식으로 조건을 수정하면 문제를 해결하기 어렵거나 쉽게 만들 수 있습니다(직관적으로 긍정적인 답변을 정당화하는 것은 더 어렵지만 부정적인 답변을 정당화하는 것은 더 쉬울 수 있습니다).Kurtz와^[34] Simon은 위의 문제가 사실상 결정 불가능하고 산술적 계층, 특히 δ-완전이라는⁰
₂ 것을 증명했다.이 경도 결과는 ^[35]계수 P를 6480으로 고정함으로써 함수 g의 클래스를 제한해도 유지된다.

대중문화에서

영화 인센디스에서 순수 수학 대학원생이 대학생들에게 콜라츠 추측을 설명한다.그녀는 가족의 과거에 대한 풀리지 않은 의문점들을 해결하기 위해 공부를 잠시 보류한다.영화 후반부에서 콜라츠의 추측은 그녀가 가족에 ^[36][37]대해 하는 불안하고 어려운 발견을 암시하는 것으로 드러난다.

「 」를 참조해 주세요.

Wikimedia Commons에는 콜라츠 추측과 관련된 미디어가 있습니다.

• 3x + 1 반군
• 산술 역학
• 모듈식 산술
• 잔차 클래스별 아핀 그룹

추가 정보

• 궁극의 과제: 3x+1 ^[10]문제는 2010년 미국 수학 협회에 의해 출판되고 제프리 라가리아스에 의해 편집된 것으로 콜라츠 추측, 접근 방법 및 일반화에 대한 정보의 요약이다.여기에는 문제의 역사, 일반화, 통계적 접근법 및 계산 이론의 결과에 관한 편집자의 조사 논문 2편과 다른 저자의 조사 논문 5편이 포함된다.그것은 또한 로타 콜라츠의 논문을 포함하여 이 주제에 관한 초기 논문의 전재본을 포함한다.

레퍼런스

외부 링크

• Matthews, Keith. "3 x + 1 page".
• David Bainaina가 진행 중인 분산 컴퓨팅 프로젝트는 큰 가치를 위해 Collatz 추측의 수렴을 검증하고 있습니다.(현재까지의 가장 큰 진전)
• 분산 컴퓨팅(BOINC) 프로젝트: 더 큰 가치를 위해 Collatz 추측을 검증합니다.
• Eric Roosendal이 진행 중인 분산 컴퓨팅 프로젝트는 점점 더 큰 가치를 얻기 위해 Collatz의 추측을 검증합니다.
• Tomas Oliveira e Silva가 진행 중인 또 다른 분산 컴퓨팅 프로젝트에서는 (Eric Roosendaal의 페이지보다 통계는 적지만 더 진전된) Collatz 추측을 계속 검증하고 있습니다.
• Weisstein, Eric W. "Collatz Problem". MathWorld.
• PlanetMath의 콜라츠 문제..
• Nochella, Jesse. "Collatz Paths". Wolfram Demonstrations Project.
• Eisenbud, D. (8 August 2016). Uncrackable? The Collatz conjecture (short video). Numberphile. Archived from the original on 2021-12-11 – via YouTube.
• Eisenbud, D. (August 9, 2016). Uncrackable? Collatz conjecture (extra footage). Numberphile. Archived from the original on 2021-12-11 – via YouTube.
• Alex Kontorovich [de] (featuring) (30 July 2021). The simplest math problem no one can solve (short video). Veritasium – via YouTube.
• 컴퓨터는 다루기 힘들기로 악명 높은 이 수학 문제를 풀 준비가 되어 있는가?