collatz conjecture(콜라츠의 추측)에 대하여

콜라츠의 추측은 아래 단순한 규칙으로 반복하였을때 모두 1로 귀결된다는 추측이다.

 

if n is odd, get 3n+1

if n is even, get n/2

 

초등학생도 이해할 수 있는 문제이기 때문에, 아이들과 같이 이야기하다가 도움이 될 수 있는 만한 정보를 확보하여 기록해 둔다. 상기 계산을 숫자별로 계속 반복한 다이어그램이 바로 아래와 같다.

[from somewhere on internet site]

그런데 이 그림을 조금 계량해 보면, 이 문제를 더 단순화 할 수 있다. 어떻게? 특정 홀수들의 2의 x제곱을 각각의 줄로 나열해놓고 표기하는 방법이다. 이렇게 되면 해당 줄에 들어서면 나누기 2를 반복해서 결국 그 홀수로 귀결된다. 그러면 그 홀수에서 3n+1로 jump하는 식으로 구성할 수 있다.

 

[even numbers & multiply by 2^x]

 

위 그림에서 아예 홀수를 순서대로 나열하는 그림으로 바꾸면 아래와 같은 그림으로 전환된다.

 

[sequantial even number & mulply by 2^x of each, then jump to 3n+1]

 

그런데 가만히 살펴보면 이 화살표를 더 단순화 할 수 있다는 것을 알 수 있다. 일단 어느 홀수 선에든 닿으면 그것은 최종의 맨 상단의 본질적인 홀수로 닫게 되고, 그것이 다시 3n+1 jump를 해도 결국 그 jump한 홀수 선의 맨 처음으로 다시 귀결하기 때문이다. 따라서 아래와 같이 그려도 사실 어느 곳으로 움직이냐를 단순화 시켜 나타낼 수 있다.

 

[simplification of previous movement arrows]

 

이것을 더 크게 나타내보면 아래와 같다. 이번에는 even*2^x 패턴에서 이 even값들만 나열해보자. 그러면 더 간단히 나타낼 수 있다.

 

보다보면 오른쪽으로 이동이나 빨간색 왼쪽 이동은 일정 패턴이 있다는 것을 알 수 있다. 다만 어려운 것은 주황색의 왼쪽 움직임이다. 이 왼쪽 움직임은 몇가지 확인을 해본 결과 3*n을 빼놓고는 모두 닿으면서 다소 불규칙하다. 그래서 사실은 이 주황색의 움직임을 정형화 할 수 있다면 콜라츠의 추측 전체를 증명할 수 있지 않을까 싶었다. 그리고 이 이동이 사실은 테렌스 타오의 증명에 나오는 함수와 연관이 있다는 사실을 알게 되었다. 이 주황색의 움직임은 결국 소수와 연관이 있지 않을까? 그래서 불규칙한가? 라는 생각도 했었다.

 

[larger diagram of previous movement arrows - irregular orange arrows]

 

이 작업을 진행하면서 3n+1 규칙 대신에 5n+1, 7n+1, 9n+1, 11n+1 등의 규칙을 조사해보았는데, 이런 확장에 대해 다소 규칙성이 있다.  새로운 규칙들에 대해 아래 숫자들을 발견하였다.

 

3n+1 -> 8n + (7-3)

5n+1 -> 8n + (8-5)

7n+1 -> 8n + (8-7)

9n+1 -> 16n + (16-9)

11n+1 -> 16n + (16-11)

 

다만 5n+1, 7n+1 등 일때는 순환이 다양한 양상으로 전개되고, 규칙 패턴이 조금씩 다르게 나타난다(검은색, 빨간색의 패턴이 다르다)

 

[movement arrows for "5n+1 and n/2 rules"]

 

[movement arrows for "7n+1 and n/2 rules"]

 

[movement arrows for "11n+1 and n/2 rules"]

 

이 정보만으로 증명하기는 어렵지만 문제를 이해하는데 조금더 단순화한 그림을 제공할 수 있다고 생각한다.

 

이 문제에 대한 짧은 유투브 동영상을 같이 공유한다. 위 패턴중 주황색 패턴을 이해하여 이 문제의 증명에 도움을 받는이가 생겼으면 좋겠다.

 

https://www.youtube.com/watch?v=094y1Z2wpJg