One More Peg, and the Formula Breaks

The tidy version, and where it ends

The Tower of Hanoi is the puzzle every recursion lesson reaches for. Three pegs, a stack of disks, one rule: never rest a larger disk on a smaller one. Move the whole stack from the first peg to the last and the shortest possible solve is famously exact, 2ⁿ − 1 moves for n disks. Sixty-four disks, the number in the temple legend, is about eighteen quintillion moves, which is the entire point of the legend.

That formula is so clean it is easy to forget how special it is. It exists because with three pegs there is essentially one strategy and no choices: to move n disks you must first move the top n − 1 out of the way onto the only spare peg, move the base, then move the n − 1 back. There is nowhere else for them to go. The recursion has a single branch, and a single branch gives you a formula.

Now hand the puzzle a fourth peg.

Play it

The board below has four pegs. Rebuild the stack on peg D. That extra column is not decoration, it is a second place to stash disks, and it changes everything. Dial the disk count, then press watch it solve to see the machine play its shortest line, and notice what the count already tells you: the four-peg minimum runs well under the three-peg 2ⁿ − 1 for the very same stack.

The solver is doing something the three-peg game never allowed. It splits the stack in two. It carries a top batch of disks out of the way onto a spare peg, using all four pegs to do it efficiently, clears the disks underneath with the three pegs that are left, then brings the batch back down onto the goal. Two spare pegs mean the top batch no longer has to be a single tower of n − 1. It can be any size you like. And "any size you like" is exactly the trouble.

The cost collapses

Module 02 puts the two counts on one log axis. The ember line is the pure three-peg exponential, a straight climb because 2ⁿ − 1 doubles with every disk. The ice line is the four-peg count, and it is barely a slope. The distance between them is not a fixed discount, it is a gap that widens forever: at 8 disks the fourth peg saves you roughly 8-fold, at 16 disks it is a few hundred fold, and by 22 disks a million-move three-peg ordeal has become a few hundred moves. One extra peg does not make the puzzle a bit easier. It changes what kind of function the answer is.

But the ice line has no formula printed over it, and that is the real story.

The split you have to tune

With a fourth peg the recursion sprouts a choice. To move n disks you pick a split k: carry the top k aside onto a spare, clear the bottom n − k on three pegs, carry the k back. Carrying k costs 2 · FS₄(k) (there and back, and it gets to use all four pegs). Clearing the base costs the old 2ⁿ⁻ᵏ − 1. So the cost of a plan is

FS₄(n) = min over k of [ 2 · FS₄(k) + (2ⁿ⁻ᵏ − 1) ]

and the shortest solve is whichever k makes that smallest. This is the Frame-Stewart recurrence, and it is a genuinely different animal from 2ⁿ − 1. There is no closed formula here, only a minimisation that calls itself. Module 03 draws the cost of every split for the stack you dial: each bar is one plan, ice for the carry, ember for the base clear, and the shortest bar is the only one worth playing.

Watch where that shortest bar sits as you grow the stack. The three-peg habit says "carry n − 1, move the base, carry n − 1 back," so you might expect the best split to hug the right edge. It does not. The optimal batch grows, but slowly, climbing a staircase while the base it leaves behind grows too. At ten disks the machine carries a batch of six and clears a base of four; the naive "n − 1" plan would cost far more. The split is tuned, and it has to be recomputed for every size, because the best k for n disks leans on the best k for every smaller stack underneath it.

The part that took seventy-three years

Here is the honest wrinkle, the reason this is a better story than "add a peg, save moves." Frame and Stewart each wrote this recurrence down in 1941, independently, in the same journal, and each conjectured its minimum was the true shortest solve. Conjectured, not proved. It is easy to show the Frame-Stewart split is a valid strategy that achieves that count. It is fiendishly hard to show no cleverer strategy, one that does not split the stack into a clean top batch and bottom batch at all, could ever beat it.

That gap stayed open for seventy-three years. Only in 2014 did Thierry Bousch prove the Frame-Stewart number really is optimal for the four-peg puzzle. (For five pegs and up, it is still a conjecture.) A puzzle simple enough for a child's toy, with one obvious-looking recurrence, hid an optimality question that outlasted the people who asked it.

You do not have to take the proof on faith for small stacks. Before this drop shipped, a brute-force search walked the entire graph of positions, all 4ⁿ of them, and found the true shortest solve by breadth-first search with no strategy assumed. For every stack up to nine disks it landed on exactly the Frame-Stewart number, move for move. The neat theory the extra peg broke turns out to be right after all. It just took the better part of a century, and a graph with tens of thousands of rooms, to be sure.

How this was made, and what was checked

Everything here is integer-exact and recomputed in your browser, so there is nothing to trust that the page cannot re-derive. Before a word was written, the claims were verified offline (every assertion passed):

• The Frame-Stewart values. FS₄(n) = min over k of [ 2·FS₄(k) + (2ⁿ⁻ᵏ − 1) ] reproduces the known sequence 1, 3, 5, 9, 13, 17, 25, 33, 41, 49, 65, …
• The solve is real. The four-peg move list (carry the top batch on all four pegs, clear the base on three, carry it back) is legal at every step, ends with the whole stack on the goal peg, and has length exactly FS₄(n), checked for n up to 12.
• The optimum is genuine, not just the best split. An exhaustive breadth-first search over all 4ⁿ positions returns the same shortest count as Frame-Stewart for every n from 1 to 9. That is Bousch's 2014 theorem, made tactile.

The three-peg board, the disk colour ramp, and the watch-it-solve animation are reused from the three-peg puzzle. The new pieces are the Frame-Stewart DP with its argmin split, the four-peg recursive solver, and the two live charts. External facts are only settled history: Frame and Stewart's independent 1941 papers and conjecture, and Bousch's 2014 proof for the four-peg case.