짝수면 2로 나누고 홀수면 3을 곱하고 1을 더한다. 어떤 수에서 시작해도 1에 도달한다는 게 Collatz 추측이다. 1에 닿을 때까지 몇 번 걸리는지를 센다.
한 수에 대해
def collatz(n, l=0):
if n == 1:
return l
elif n % 2 == 0:
return collatz(n // 2, l + 1)
else:
return collatz(n * 3 + 1, l + 1)
정의를 그대로 옮겼다. 반복문으로도 같다.
while n != 1:
if n % 2 == 0:
n //= 2
else:
n = n * 3 + 1
cnt += 1
범위 전체를 훑을 때
1부터 100만까지 중 가장 긴 것을 찾으려면 이야기가 달라진다. 각 수를 따로 계산하면 같은 구간을 몇 번이고 다시 지난다.
어떤 수든 몇 단계만 가면 이미 계산해본 작은 수로 떨어진다. 거기서부터는 답이 이미 있다.
def collatz(n):
if d.get(n):
return d[n]
if n % 2 == 0:
d[n] = 1 + collatz(n // 2)
return d[n]
else:
d[n] = 1 + collatz(n * 3 + 1)
return d[n]
d = {1:1}
for i in range(s, e + 1):
collatz(i)
print(f'Number: {max(d, key=d.get)}, Longest Cycle Length: {max(d.values())}')
d 에 있으면 그대로 꺼내고 없으면 한 단계 내려가 계산한다. d[1] = 1 이 바닥이다.
결과
Number: 837799, Longest Cycle Length: 525
100만 아래에서 837799가 가장 길다. 1을 포함해 525개의 수를 거친다.
딕셔너리가 범위보다 커진다
d 의 크기를 세어보면 2168611개다. 100만까지 훑었는데 항목이 두 배 넘게 쌓인다.
홀수에 3을 곱하면 범위 밖으로 나가기 때문이다. 837799에서 시작하면 중간에 2974984576까지 올라갔다 내려온다. 그렇게 잠깐 들른 큰 수들도 전부 저장된다.
범위 안의 답만 알면 되는데 범위 밖의 것까지 다 들고 있는 셈이다. 범위를 넘어가는 값은 저장하지 않도록 막으면 메모리는 줄지만, 그 값을 다시 만났을 때 또 계산해야 한다.
max(d, key=d.get) 도 마찬가지다. d 전체에서 최댓값을 찾으므로 범위 밖의 수가 답으로 나올 수 있다. 여기서는 837799가 범위 안이라 문제가 안 됐다.
재귀 깊이
d.get(n) 이 없으면 한 단계씩 내려간다. 525단계짜리가 있으므로 재귀가 그만큼 깊어질 수 있다. 파이썬의 기본 재귀 한도가 1000이라 이 범위에서는 아슬아슬하게 통과한다. 범위를 더 넓히면 한도를 올리거나 반복문으로 바꿔야 한다.