알고리즘 - 콜라츠의 추측

콜라츠의 추측

자연수 n에 대하여,
n이 짝수이면 n을 2로 나누고,
n이 홀수이면 3을 곱하고 1을 더한다.
n이 1이면 계산을 멈춘다.
이런 식의 계산을 반복하면 어떤 자연수든 반드시 1이 된다.

콜라츠의 추측을 코드로 만들면 아래와 같다.

def collatz(n):
    seq = [n]       # 수 들을 담을 리스트
    
    while n > 1:
        if n % 2 == 0:        # n이 짝수일때
            n = n // 2
        else:                 # n이 홀수일때
            n = 3 * n + 1
            
        seq.append(n)
        
    return seq               # 콜라츠의 수열

for n in range(1, 10):
    print(collatz(n))

for n in range(1, 100):
    print(len(collatz(n)), end=' ')
    
->
[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]

1 2 8 3 6 9 17 4 20 7 15 10 10 18 18 5 13 21 21 8 8 16 16 11 24 11 112 19 
19 19 107 6 27 14 14 22 22 22 35 9 110 9 30 17 17 17 105 12 25 25 25 12 12 
113 113 20 33 20 33 20 20 108 108 7 28 28 28 15 15 15 103 23 116 23 15 23 23
36 36 10 23 111 111 10 10 31 31 18 31 18 93 18 18 106 106 13 119 26 26 

콜라츠의 수열은 규칙성이 없기 때문에 수학적으로 증명하지 못했다. 이를 우박수 문제라고 부르기도 한다.

---

문제 1

콜라츠 수열의 길이가 100인 숫자들 중에서 가장 작은 수는?

n = 0

while True:         # 무한루프
    n += 1          # n을 1씩 증가시킨다.
    halestone = collatz(n)
    if len(halestone) == 100:       # 콜라츠 수열의 길이가 100면 멈춘다.
        break
        
print(halestone)
print('길이가 100인 가장 작은 수 :', n)

->
[322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 
175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 
566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 
3644, 1822, 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, 53, 160, 80, 40, 20, 10, 5,
16, 8, 4, 2, 1]
길이가 100인 가장 작은 수 : 322

---

문제 2

10000 이하의 자연수 중에서 콜라츠 수열의 길이가 가장 긴 수는? 그리고 그 길이는?

max = 0
c_length = 0

for n in range(1, 10001):
    if len(collatz(n)) > c_length:     # 콜라츠 수열의 길이가 가장 길면
        max = n                        # 가장 긴 수를 바꿔준다.
        c_length = len(collatz(n))     # 길이의 값을 바꿔준다.
    
print('콜라츠 수열의 길이가 가장 긴 수 :', max)
print('길이 :', c_length)

->
콜라츠 수열의 길이가 가장 긴 수 : 6171
길이 : 262

---

문제 3

콜라츠 수열의 길이가 500보다 큰 첫번째 자연수는?

n = 0

while True:
    n += 1
    halestone = collatz(n)
    if len(halestone) > 500: 
        break

print(len(halestone))
print('길이가 500보다 큰 첫번째 자연수 :', n)

->
509
길이가 500보다 큰 첫번째 자연수 : 626331

---

문제 4

콜라츠 수열의 길이가 500보다 큰 열번째 자연수의 콜라츠 수열 길이는?

n = 0
c_list = []

while True:
    n += 1
    halestone = collatz(n)
    if len(halestone) > 500: 
        c_list.append(len(halestone))
    
    if len(c_list) == 10:
        break

print(c_list)
print('길이가 500보다 큰 열번째 자연수의 콜라츠 수열 길이 :', c_list[-1])

->
[509, 504, 525, 507, 502, 528, 528, 510, 510, 523]
길이가 500보다 큰 열번째 자연수의 콜라츠 수열 길이 : 523

** 출처

• 주니온TV 아무거나연구소 - 코린아, 코딩하자 (with 파이썬)