[python/알고리즘] 콜라츠의 추측

 

콜라츠의 추측이란?

---

1937년 Collatz란 사람에 의해 제기된 추측으로 주어진 수가 짝수이면 2로 나누고, 홀수이면 곱하기3을 한 다음 1을 더하는 작업을 반복하면 모든 수를 1로 만들 수 있다고 제시한 수학적 명제이다.

 

1. python 코드로 구현

  
  def collatz(n):
      seq = [n]
      while (n > 1):  # 주어진 수 n이 1보다 클 때까지 반복
          if n % 2 == 0 :  # 짝수인 경우
              n = n // 2
          else:  # 홀수인 경우
              n = 3 * n + 1
          seq.append(n)
      return seq
      

-> seq 리스트에 append 함으로써 콜라츠의 수열을 볼 수 있다. 마지막은 1이 나온다.

 

---

 

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

A.

  
  n = 1
  while True:
      res = len(collatz(n))
      if res == 100 :
          print(n)
          break
      else:
          n += 1
          

-> 1부터 순차적으로 증가하며 위의 사용자 함수를 가져와 list의 길이가 100인 경우 출력하고 종료한다.

 

Q. 10,000 이하의 자연수 중에서 콜라츠 수열의 길이가 가장 긴 수와 길이는?

A.

  
  # 내가 푼 것
  res_seq = []
  for i in range(1,10001):
      res_seq.append(len(collatz(i)))

  print(res_seq.index(max(res_seq)) + 1)
  print(max(res_seq))
  

-> 빈 리스트에 1부터 10000까지의 콜라츠의 수열 길이를 추가한다.

    리스트 중 가장 큰 값(max)을 출력 : 콜라츠의 수열 길이가 가장 긴 길이 수

    리스트 중 가장 큰 값의 인덱스 + 1 : 콜라츠의 수열의 길이가 가장 긴 수

 

   
  # 강의 코드
  maxlen = 0
  maxseq = []
  for n in range(1, 10001):
      halestone = collatz(n)
      length = len(halestone)
      if maxlen < length :
          maxlen = length
          maxseq = halestone

  print('우박수 : ',maxseq[0])
  print('우박수의 길이 : ', maxlen)
    

-> 콜라츠의 수열의 길이를 구한 후 길이를 length에 저장한다.

   length가 maxlen 보다 크다면 maxlen을 교체하며 mexseq에 수열 길이의 대상이 되는 숫자를 저장한다.

 

우박수(hailstone number)란?

---

콜라츠의 수열을 말하며, 아래는 1부터 50,000까지의 콜라츠의 수열로 결국 1로 수렴하기에 아래와 같이 우박수의 형태로 표현되어 우박수라 불리게 되었습니다.

 

 

출처 : Youtube 주니온TV 아무거나연구소의 코린아, 코딩하자! with 파이썬