Daily Algorithm - Day 13

Longest Collatz Sequence

The following iterative sequence is defined for the set of positive integers:
$n → n / 2$ ($n$ is even)
$n → 3 n + 1$ ($n$ is odd))

Using the rule above and starting with 13, we generate the following sequence:
$13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1$

It can be seen that this sequence (starting at $13$ and finishing at $1$) contains terms.
Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at $1$.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

100만 이하의 수로 콜라츠 추측을 진행했을 때, 가장 긴 변환횟수를 가진 수를 구하는 문제이다.

처음으로 생각해낸 구현 방식은 다음과 같다.

1. for 반복문을 통해 100만 이하의 수를 모두 계산.
2. 100만 이하의 모든 수에 대해 while 반복문을 통해 숫자와 과정횟수를 출력해준다.
3. list를 활용해 출력된 count 값을 정렬하고 가장 큰 값을 찾는다.

바로 코드를 작성해보자.

//Python

collatz = []

for num in range(1, 1000001):
	n = num  # 현재 숫자를 n에 저장 (n은 계산 과정에서 변화됨)
    count = 0  # 변환 횟수를 저장하는 변수 초기화
    
    # 콜라츠 추측 계산 시작 (n이 1이 될 때까지 반복)
    while n != 1:
        if n % 2 == 0:
            n = n / 2
        else:
            n = 3*n + 1
        count += 1
    collatz.append((count, num)) # sort()했을 때 count가 가장 큰 값이 제일 뒤로 갈 수 있게
    

print(sorted(collatz)[-1])

>>> (524, 837799)

답은 837799, 과정횟수는 524회다. 이대로는 뭔가 아쉬우니 과정횟수가 가장 큰 숫자가 갱신되면 해당 사실을 출력하는 기능까지 추가해보자. 그리고 이번엔 list를 사용하지 않고 구현을 해보자. 처음부터 while 반복문을 사용한다면 좋을 것 같다.

num = 1
max_count = 0  # 가장 많은 과정횟수
max_num = 0  # max_count를 가진 수

while num <= 1000000:
    n = num  # 현재 숫자를 n에 저장 (n은 계산 과정에서 변화됨)
    count = 0  # 변환 횟수를 저장하는 변수 초기화
    
    # 콜라츠 추측 계산 시작 (n이 1이 될 때까지 반복)
    while n != 1:
        if n % 2 == 0:
            n = n / 2
        else:
            n = 3*n + 1
        count += 1
    
    # 현재 숫자의 변환 횟수가 이전 최댓값보다 크다면 갱신
    if max_count < count:
        print(f"number changed! ({max_num}: {max_count} times -> {num}: {count} times)")
        max_count = count
        max_num = num    
    num += 1

print(f"{max_num}: {max_count} times")

>>> 
number changed! (0: 0 times -> 2: 1 times)
number changed! (2: 1 times -> 3: 7 times)
number changed! (3: 7 times -> 6: 8 times)
.
.
.
number changed! (410011: 448 times -> 511935: 469 times)
number changed! (511935: 469 times -> 626331: 508 times)
number changed! (626331: 508 times -> 837799: 524 times)
837799: 524 times

오늘은 여기까지.

-2025.01.02-