[파이썬/법칙] 콜라츠 추측

재미있는 것이라서 파이썬으로 만들어 봤습니다.

 

[콜라츠 추측(collatz conjecture)]
- 1937년 Collatz란 사람에 의해 제기된 추측
규칙>
   1. 입력된 수가 짝수라면 2로 나눕니다. 
   2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다. 
   3. 1이 될 때까지 반복 (1->4->2->1 반복)
예>
  - 수가 13이라면 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 이 1 이 됩니다.
  - 마지막 1은 홀수여서 1*3+1=4가 되고, 4/2=2가 되고, 2/2=1 로 되어 반복됩니다.
문제>
  - 반례를 찾지 못함


참고>
https://ko.wikipedia.org/wiki/%EC%BD%9C%EB%9D%BC%EC%B8%A0_%EC%B6%94%EC%B8%A1

 

다음과 같이 간단한 코드를 만들어 봤습니다.

import random
import matplotlib.pyplot as plt

def collatz(num):
    loop = []
    for i in range(500):    # 500 번까지만 수행
        loop.append(int(num))
        if num == 1:         # 1이면 종료( 1 * 3( + 1) = 4 / 2 = 2 / 2 = 1 (반복)
            break
        elif num % 2 == 0:    # 짝수면
            num = num/2      # 2로 나눔
        elif num % 2 == 1:  # 홀수면 
            num = (num*3)+1  # * 3 + 1
    return loop

data = []      # 콜랕츠추측 path
data_len = []  # 추측의 단계수
for i in range(10):
    # n = random.randrange(1, 100)
    n = i + 1
    rtn = collatz(n)
    data.append(rtn)
    data_len.append(len(rtn))
    print(rtn)

결과는 다음과 같습니다.

[1]
[2, 1]
[3, 10, 5, 16, 8, 4, 2, 1]
[4, 2, 1]
[5, 16, 8, 4, 2, 1]
[6, 3, 10, 5, 16, 8, 4, 2, 1]
[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
[8, 4, 2, 1]
[9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
[10, 5, 16, 8, 4, 2, 1]

 

그래프까지 포한된 코드 입니다.

### Full code
import random
import matplotlib.pyplot as plt

def collatz(num):
    loop = []
    for i in range(500):    # 500 번까지만 수행
        loop.append(int(num))
        if num == 1:         # 1이면 종료( 1 * 3( + 1) = 4 / 2 = 2 / 2 = 1 (반복)
            break
        elif num % 2 == 0:    # 짝수면
            num = num/2      # 2로 나눔
        elif num % 2 == 1:  # 홀수면 
            num = (num*3)+1  # * 3 + 1
    return loop

data = []      # 콜랕츠추측 path
data_len = []  # 추측의 단계수
for i in range(100):
    # n = random.randrange(1, 100)
    n = i + 1
    rtn = collatz(n)
    data.append(rtn)
    data_len.append(len(rtn))
    print(rtn)

%matplotlib Qt5
# %matplotlib inline
plt.rcParams['font.family'] = 'NanumGothic'    # 한글 사용
fig = plt.figure(figsize=(14, 7))
for i in range(len(data)):
    plt.plot(data[i], label='loop' + str(i+1))
plt.title('MAX step=' + str(max(data_len)))
# plt.legend()
plt.grid()
plt.show()

모두 step이 진행되면서 널뛰다가 1로 됩니다.