프로젝트 오일러 014

콜라츠 수열은 ‘우박수’라는 이름으로 더 많이 알려져 있습니다. 수열 자체는 앞 항이 홀수인지 짝수인지에 따라 점화식이 달라지며, 그 식 자체는 매우 간단합니다.

1. 어떤 수가 짝수라면 다음 수는 그 수를 2로 나눈 몫입니다.
2. 어떤 수가 홀수라면 다음 수는 그 수에 3배하고 1을 더한 값입니다.

어떤 수로부터 이 수열을 계속 전개해나가면 1에 이루는 것으로 추측됩니다. 1에 다다르는 과정은 다음과 같습니다.

• 어떤 수가 홀수라면 그 다음번 수는 항상 짝수가 됩니다.
• 어떤 수가 짝수이면서 2의 거듭제곱에 해당한다면 계속 짝수 루트를 타서 1에 도달하게 됩니다.

점화식

어떤 수열에 대해 점화식이 알려져 있다면, 재귀를 통해서 표현하는 것이 가능합니다. 재귀를 사용하기 위해서는, 두 가지 조건이 필요한데 첫째로 기저 케이스로 반복의 종료가 되거나, 수열의 첫 시작을 의미하기도 합니다. 다음은 이전 혹은 이후 값을 변형하여 현재 항을 계산하는 점화식입니다.

어떤 수 N으로부터 시작하여 1에 도달하는 진행 과정의 수를 나타내는 수열을 F(N)이라 한다면, 이는 다음과 같이 파이썬 코드로 표현할 수 있습니다.

def F(n):
	if n == 1:
		return 1
	if n % 2 == 0:
		return F(n // 2) + 1
	return F(n * 3 + 1) + 1

그런데, 재귀를 사용하는 경우에는 몇 가지 제약이 따릅니다. 파이썬에서 재귀의 반복 깊이는 일반적으로 1000번입니다. 그러니 1까지 가는 과정의 길이가 1,000보다 큰 경우에는 재귀 깊이 제약으로 코드가 실행되지 않게 됩니다. 그러니 다음과 같이, 반복문을 사용하는 형태로 바꾸어 구현할 수도 있습니다. 사실 재귀와 루프는 같은 구조이기 때문에 모든 재귀는 루프로, 모든 루프는 재귀로 구현할 수 있음이 수학적으로도 증명되어 있습니다.

우박수

우박수 과정을 따라가는 알고리듬은 간단합니다. 짝수일 때는 절반으로 내려가고, 짝수 일 때는 3배 + 1로 올라갑니다.

def F(n):
  c = 1
  while n > 1:
    if n % 2 == 0:
      n = n // 2
    else:
      n = n * 3 + 1
    c += 1
  return c

이 단순한 과정을 반복하면 n의 우박수 길이를 알 수 있지만, 문제는 1백만 이하의 수에 대해서 우박수 경로 길이를 모두 구해야 그 최대값을 알 수 있다는 것입니다.

print(max((F(n), n) for n in range(1, 200_0001))[1])

그런데 이 방법은 매우 느리기 때문에 시간을 단축할 수 있는 최적화 방법을 찾아야 합니다.

캐시

백만 이하의 모든 수에 대해 이 과정을 추적하는 것은 상당한 시간이 필요할 것으로 예상됩니다. 소수 판정 같은 경우에는 이런 저런 최적화할 수 있는 지식이 동원되었습니다만, 우박수에 대해서는 예측이 힘든 부분이 많아 더 이상의 최적화는 어려울 것으로 예상됩니다. 하지만 이런 수열과 관련된 문제에서는, “어? 한 번 계산한 걸 또?”하는 시점이 있습니다.

예를 들어 200과 33을 봅시다. 200의 다음 항은 100입니다. 33의 다음항도 100입니다. 이는 200과 33이 같은 우박수 길이를 갖는다는 사실보다, 33에 대해 우박수 길이를 계산해보면, 다른 숫자의 우박수 길이에 대해서도 알게 된다는 것입니다. 실제로 33부터 시작하는 우박수열은 제법 긴 과정을 거치며, 다음과 같은 수가 등장합니다.

• 33 > 100 > 50 > 25 > 76 > 38 > 19 > 58 > 29 > 88 > 44 > 22 > 11 > 34 > 17 > 52 > 26 > 13 > 40 > 20 > 10 >
• 5 > 16 > 8 > 4 > 2 > 1

이 과정에서 34가 등장하니, 34의 우박수 과정은 사실상 계산할 필요가 없을 수 있습니다. 이전에 벌써 계산해본 적이 있으니까요. 이처럼 이미 계산한 값을 기록해두었다가 사용하는 것을 ‘메모이제이션’이라고 합니다.

cache = [1:1]

def F(n):
	if n in cache:
		return cache[n]
	r = (F(n // 2) if n % 2 == 0 else F(n * 3 + 1)) + 1
	cache[n] = r
	return r

메모이제이션으로 이 과정의 계산을 반복하지 않으려면 중간 계산 결과에서도 캐시된 값을 사용할 수 있어야하기 때문에 반복문 보다는 재귀 형식으로 코드를 작성해야 효과가 있습니다. 계산 과정에서 발생하는 값에 대한 계산 결과 역시, 계속해서 캐시되므로 계산이 진행될수록 캐시가 적중하는 비율이 올라가며 시간 단축 효과가 더 많이 발생할 것입니다.

초기 캐시

N이 짝수인 경우에는 2로 나누는 연산을 합니다. 따라서, 2, 4, 8, 16, .. 등 2의 거듭제곱수들은 계속 절반으로 나눠진 후 1에 도달하게 됩니다. 즉 $2^n$인 수는 $n+1$의 길이의 우박수 경로를 갖습니다. 이는 계산해보지 않아도 알 수 있으므로 미리 캐시에 기록하여 성능을 향상시킬 수 있습니다.

cache = {2**n:n + 1 for n in range(30)}

def F(n):
	if n in cache:
		return cache[n]
	r = (F(n // 2) if n % 2 == 0 else F(n * 3 + 1)) + 1
	cache[n] = r
	return r

정렬하기

이 문제는 최대가 되는 단계의 수를 구하는 것이 아니라, 단계의 수가 최대인 값을 구하는 문제입니다. max() 함수는 개별 값 뿐만 아니라 짝지어진 튜플도 비교할 수 있습니다. 튜플의 비교는 첫번째 요소부터 비교하고, 첫번째 요소가 같다면 그 다음 요소를 순서대로 비교합니다. 따라서 (F(n), n) 을 비교하여 최대치를 구하면 F(n)이 최대일 때의 n도 알 수 있게 됩니다.

print(max((F(n), n) for n in range(1, 100_0001))[1])