하노이 탑 계산기

원판이 n개면 2ⁿ − 1번입니다. 3개면 7번, 5개면 31번, 10개면 1,023번, 20개면 1,048,575번입니다. n−1개를 옆 기둥으로 치우고, 가장 큰 것을 한 번 옮기고, 다시 얹는 구조라 T(n) = 2·T(n−1) + 1이 되고 이것을 풀면 2ⁿ − 1이 나옵니다. 이보다 적게 옮길 방법이 없다는 것도 증명되어 있습니다.

1초에 한 번씩 쉬지 않고 옮겨도 약 5,846억 년이 걸립니다. 이동 횟수가 2⁶⁴ − 1 = 18,446,744,073,709,551,615번이기 때문입니다. 우주 나이 138억 년의 마흔두 배쯤 되는 시간입니다. 흔히 5,845억 년으로 인용되는데, 그레고리력 평균년(31,556,952초)으로 정확히 나누면 584,554,049,254년입니다.

엄청나게 줄어듭니다. 원판 64개가 기둥 3개에서는 1,844경 번이지만 기둥 4개에서는 18,433번뿐입니다. 5,846억 년이 다섯 시간으로 바뀌는 셈입니다. 이 값은 프레임-스튜어트 알고리즘으로 구하며, f(n,p) = min(2·f(k,p) + f(n−k,p−1))을 따릅니다. 다만 이것이 최소라는 일반 증명은 아직 없고, 작은 원판 수에서 전수 확인으로만 최적임이 알려져 있습니다.

가장 작은 원판을 한 방향으로 계속 돌리고, 그 사이사이에 가능한 유일한 수를 두면 됩니다. 원판 수가 홀수면 작은 원판을 A→C→B→A 방향으로, 짝수면 A→B→C→A 방향으로 옮깁니다. 홀수 번째 이동은 항상 가장 작은 원판 차례이고, 짝수 번째에는 작은 원판을 건드리지 않는 수가 하나뿐이라 고민할 것이 없습니다.

알 수 있습니다. k를 2진수로 썼을 때 뒤에 붙은 0의 개수에 1을 더한 번호입니다(1번이 가장 작은 원판). 예를 들어 8번째 이동은 8 = 1000₂이라 0이 셋 붙었으니 4번 원판입니다. 홀수 k는 0이 하나도 없으므로 늘 1번 원판이 되고, 이것이 홀수 번째마다 작은 원판이 움직이는 이유입니다.

i번 원판은 2^(n−i)번 움직입니다(1번이 가장 작은 원판). 가장 작은 원판이 2^(n−1)번으로 전체의 절반을 차지하고, 가장 큰 원판은 딱 한 번만 움직입니다. 모두 더하면 2⁰ + 2¹ + … + 2^(n−1) = 2ⁿ − 1로 전체 횟수와 정확히 맞습니다.