(정수론/파이썬) 3*n + 1 알고리즘

# '친절한 수론 길라잡이' 36쪽 연습문제 5.5
# 3*n + 1 알고리즘
# 임의의 숫자 n에서 시작한다. n이 짝수이면 2로 나누고, n이 홀수라면 3n + 1로 대체한다.
# 이를 반복하여 하나의 수열을 얻는다. 예를 들어, 5에서 시작했다면
# 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, ...
# 7에서 시작했다면
# 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1...
# 을 얻는다. 만일 수열에 4가 나타나면 계속 4, 2, 1이 반복해서 나타나는 것을 확인할 수 있다.
# 일반적으로는 다음 두 가지 경우가 가능하다.
# 1) 몇 개의 수가 반복하여 나오는 경우이다. 이 경우 우리는 이 알고리름이 반복되지 않는 마지막 값에서
# 종료된다고 말하고, 이 수열에 타나나는 서로 다른 수의 개수를 알고리즘 길이라고 정리한다. 예를 들어,
# 5와 7의 경우에는 모두 1에서 종료되고, 5에 대한 알고리즘의 길이는 6, 7에 대한 알고리즘 길이는 17이다.
# 2) 같은 수가 절대 반복되어 나타나지 않는 경우다. 이 경우는 알고리즘이 끝나지 않는다고 말한다.

def n3_1(num):
  lst = []
  lst.append(num)
  
  while True:
    if num % 2 == 0: # 짝수라면
      num = num // 2
    else:  # 홀수라면
      num = num * 3 + 1
    if num not in lst:
      lst.append(num)
    else:
      return lst, len(lst), lst[len(lst)-1]
    
print(n3_1(5))
print(n3_1(7))
print(n3_1(21))
print(n3_1(13))
print(n3_1(31))
print(n3_1(11))
print("--------------------")

for i in range(1, 101):
  _, length, last = n3_1(i)
  print(f"{i:03d}: length: {length}, last: {last}")
  #print(_)

결과:

([5, 16, 8, 4, 2, 1], 6, 1)
([7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1], 17, 1)
([21, 64, 32, 16, 8, 4, 2, 1], 8, 1)
([13, 40, 20, 10, 5, 16, 8, 4, 2, 1], 10, 1)
([31, 94, 47, 142, 71, 214, 107, 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], 107, 1)
([11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1], 15, 1)
--------------------
001: length: 3, last: 2
002: length: 3, last: 4
003: length: 8, last: 1
004: length: 3, last: 1
005: length: 6, last: 1
006: length: 9, last: 1
007: length: 17, last: 1
008: length: 4, last: 1
009: length: 20, last: 1
010: length: 7, last: 1
011: length: 15, last: 1
012: length: 10, last: 1
013: length: 10, last: 1
014: length: 18, last: 1
015: length: 18, last: 1
016: length: 5, last: 1
017: length: 13, last: 1
018: length: 21, last: 1
019: length: 21, last: 1
020: length: 8, last: 1
021: length: 8, last: 1
022: length: 16, last: 1
023: length: 16, last: 1
024: length: 11, last: 1
025: length: 24, last: 1
026: length: 11, last: 1
027: length: 112, last: 1