14. Longest Collatz sequence

1. 개요

문제는 이곳에서 확인할 수 있다.

어떤 수열 \(a_n\)이 아래와 같은 일반항을 가진다고 하자. 

$$a_{n+1}= \begin{cases} a_{n}/2, & \text{if $n$ is even} \\ 3a_{n}+1, & \text{if $n$ is odd} \end{cases} $$

예를 들어 \(a_1=13\)인 경우 다음과 같이 항의 길이가 10인 수열을 얻는다.

$$13\rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1$$

증명되진 않았지만 모든 양의 정수인 \(a_1\)은 반드시 1로 끝난다고 알려져 있다. 이때 가장 긴 수열을 만드는 100만 보다 작은 \(a_1\)을 찾는 것이 목표이다.

2. Ver 1.0

이 문제의 특징은 메모이제이션(memoization)을 사용할 수 있다는 점이다. 즉, \(a_1=13\)의 수열의 길이를 구하면서 \(a_1=40\)의 수열의 길이도 구할 수 있다. 또한 이전에 \(a_1=10\)의 수열의 길이를 저장해 두었다면 이를 사용하여 계산에 걸리는 시간을 크게 줄일 수 있다.

# -*- coding: utf-8 -*-

sequence_length = dict()

for n in range(2, 1000000):

    if n in sequence_length:
        continue

    temp_n = n
    temp_sequence_length = dict()
    temp_sequence_length[n] = 1

    while temp_n != 1:

        if temp_n % 2 == 0:
            temp_n = temp_n // 2
        else:
            temp_n = 3 * temp_n + 1

        # 찾고자 하는 수가 기존의 sequence에 존재하면 수를 누적시킨 후 종료한다.
        if temp_n in sequence_length:
            cnt = sequence_length[temp_n]
            stop_calc = True
        else:
            cnt = 1
            temp_sequence_length[temp_n] = 0
            stop_calc = False

        for k in temp_sequence_length:
            temp_sequence_length[k] += cnt

        if stop_calc:
            break

    sequence_length.update(temp_sequence_length)

# 1000000보다 큰 키는 삭제한 후 value를 기준으로 max key를 찾는다.
sequence_length = {k: v for k, v in sequence_length.items() if k < 1000000}
max_k = max(sequence_length, key=sequence_length.get)
print(max_k)
print(sequence_length[max_k])

답은 837799이다.