14. Longest Collatz sequence

1. 개요

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

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

$$a_{n+1}=\{\begin{array}{ll}{a}_n/2,& \text{if }n\text{ is even}\\ 3a_n+1,& \text{if }n\text{ is odd}\end{array}$$

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

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

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

2. Ver 1.0

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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

# -*- 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이다.