파이썬, 콜라츠 추측 (Collatz conjecture) 문제

 

콜라츠 추측  (Collatz conjecture) 문제

 

글. 오상문 sualchi@daum.net

콜라츠 추측은 1937년에 제기한 로타르 콜라츠 이름을 딴 것이며

3n+1 추측, 울람 추측, 헤일스톤 수열 등으로도 불린다.

콜라츠 추측은 임의 자연수가 다음 단계를 거치다보면 늘 1이 된다는 것이다.

1. 짝수라면 2로 나눈다.
2. 홀수라면 3을 곱하고 1을 더한다.
3. 1이면 조작을 멈추고, 1이 아니면 첫 번째 단계로 돌아간다.

 

예제 코드는 다음과 같다.

# 어떤 양수 n이 1이 될 때까지 걸린 횟수 
def solution(n):
    answer = -1         
    for i in range(500):
      if n==1: 
          return i
      if n&1==0: n //= 2
      else: n = 3*n + 1             
    return answer
#---------------------------------

 

for n in range(1,20):
  print(n, ':',  solution(n))

 

[실행 결과]
1 : 0
2 : 1
3 : 7
4 : 2
5 : 5
6 : 8
7 : 16
8 : 3
9 : 19
10 : 6
11 : 14
12 : 9
13 : 9
14 : 17
15 : 17
16 : 4
17 : 12
18 : 20
19 : 20

<이상>