64 Rings, and 584 Billion Years at One Move a Second

Sixty-four rings of distinct sizes sit stacked on one of three pegs, widest at the bottom. Move the whole stack to another peg. You may move one ring at a time, and no ring may ever rest on a smaller one. How long does it take at one move a second?

There is a good anchor available and it is a trap. Thirty-two rings take $2^{32} - 1$ moves, which is a little over four billion seconds, which is $136$ years. That figure is correct. Doubling it because sixty-four is twice thirty-two is the mistake, and the answer it produces is wrong by a factor of four billion.

The recursion, and why it is the whole problem

Let $V(n)$ be the minimum number of moves for $n$ rings. To move $n$ rings you have to move the largest one at some point, and to do that the other $n-1$ must all be sitting on the peg you are not using. So the sequence necessarily splits into three parts.

and the closed form follows by induction, since $2(2^{n-1} - 1) + 1 = 2^n - 1$:

The part usually skipped is that (1) is an equality rather than an upper bound. Read left to right it says a strategy exists using that many moves. Read as a bound it says no strategy uses fewer, and that direction needs the argument in Fig. 1 stated as a constraint: before the largest ring can move at all, the $n-1$ smaller rings must already be stacked on a single peg, which is itself an instance of the same problem and therefore costs at least $V(n-1)$. After the largest ring is in place, the $n-1$ smaller ones must be brought onto it, another $V(n-1)$ at least. So

and with $V(1) = 1$ the induction gives $V(n) \ge 2^n - 1$. Combined with the strategy, that is an exact answer rather than a good one.

What doubling the rings actually costs

For sixty-four rings,

which is about $18.4 \times 10^{18}$ moves. The reason the linear guess fails so badly is that the ratio between the two cases is not two, and it factors exactly:

using the difference of squares on $2^{64} - 1 = (2^{32}-1)(2^{32}+1)$. So the guess of $272$ years is short by more than four billion times. This is the shape of every mistake people make with exponentials: the intuition treats $n$ as a multiplier on the cost when it is an exponent, and doubling an exponent squares the answer.

Five hundred and eighty-four billion years

Turning (4) into a duration needs one convention stated rather than assumed, because at this precision the choice of year is visible. Using the Julian year of $365.25$ days, that is $31{,}557{,}600$ seconds, and

A calendar year of exactly $365$ days would give $584.9$ billion instead, so the third digit is a convention and not a measurement. The same divisor turns $2^{32}-1$ seconds into $136.10$ years, which is where the anchor in the trap comes from.

Taking the age of the universe as $13.787$ billion years puts the answer at about $42$times that, which is the comparison I would use if I only had one sentence. The factor depends on a measured quantity, so "about forty-two" is the honest form of it.

What the number rules out

One move a second is an arbitrary rate, so it is worth asking what rate would be needed to make the task possible at all. Dividing (4) by the age of the universe in seconds gives about $42$ moves a second, sustained without a break since the beginning of time. Speed does not rescue this. Going a thousand times faster still leaves a duration of six hundred million years, and going a billion times faster leaves six centuries.

The same arithmetic settles a related question that people reach for, which is whether you could at least write the solution down. The sequence has $2^{64}-1$ entries, and even at one byte each that is eighteen exabytes, comfortably more than the total storage manufactured in a year. What saves the situation is (7) below: the sequence is compressible to a rule, so you never have to store it, only regenerate it. That is the difference between an answer of exponential size and a problem of exponential difficulty.

Which ring moves on move k

The optimal sequence has a closed form of its own, which is worth knowing because it turns the recursion into something you can execute without a stack. Number the rings from the smallest, and at move $k$ the ring that moves is

where $\nu_2(k)$ counts the trailing zeros in the binary form of $k$. For three rings that reads $1,2,1,3,1,2,1$, which is the optimal solution written out. The smallest ring moves on every odd step, so it accounts for just over half of all moves, the next ring for a quarter, and the largest ring moves exactly once, on step $2^{n-1}$. The pattern is the same one you get from the tick marks on a ruler, which is where its usual name comes from.

Add a peg and the problem changes character

The three-peg answer is elementary and exact. Allow a fourth peg and you can do far better, because the $n-1$ rings no longer have to end up on one peg before the largest moves, and the natural recursion splits the stack into two groups whose sizes you get to choose. The resulting count is much smaller and much harder to pin down: the algorithm everyone uses was proposed in 1941 and only proved optimal for four pegs in 2014. For five pegs and beyond it remains open.

I find that the most interesting fact in the neighbourhood. The version with a legend attached has a one-line answer, and the version with one extra peg was an open problem for seventy-three years.

Sources and further reading

• The puzzle, the recursion in (1) and the sequence in (7) — Tower of Hanoi
• Solving (1) in closed form — Recurrence relation
• The function in (7) — OEIS A001511 and the 2-adic valuation
• The four-peg counts — OEIS A007664
• The age used for the comparison — Age of the universe

Every figure above was checked before publication in three ways: symbolically, by a breadth-first search over the complete state graph for $n = 1$ to $12$ which confirms the count is a genuine minimum rather than an achievable one, and by a move-by-move play-out of the strategy for $n$ up to $20$ that raises on any illegal placement. Durations were computed in exact integer and rational arithmetic.