Three pegs. A stack of discs on the first, biggest at the bottom. Move the whole stack to the last peg, one disc at a time, and never put a bigger disc on a smaller one. That is the whole puzzle, and it hides one of the fastest-growing numbers in everyday computing.
Tap a peg to pick up its top disc, then tap where to put it. Start with 3 discs, then try 5. The counter shows the fewest moves that could possibly work.
To move a tower of n discs, you have to free the biggest disc. That means the n − 1 discs above it must already sit on the spare peg. So the job splits in three: move n − 1 discs out of the way, move the big disc once, then move those n − 1 discs back on top of it.
Each of those two smaller jobs is the same puzzle with one disc fewer. If T(n) is the fewest moves for n discs, then T(n) = 2 × T(n − 1) + 1. With one disc it takes 1 move, then 3, 7, 15, 31, 63. Every new disc doubles the work and adds one. The pattern is 2n − 1, and it is also the true minimum: the big disc has to move at least once, and the n − 1 discs above it have to be moved off and back on.
Drag the slider and watch the minimum move count, and how long it would take at one move per second.
The puzzle was published in 1883 by the French mathematician Édouard Lucas, who attached a legend to it: monks in a temple are moving a tower of 64 golden discs, and when they finish, the world ends. It is a story, not a record of real monks, but the arithmetic is real. The minimum for 64 discs is 264 − 1, which is 18,446,744,073,709,551,615 moves. At one move per second that is roughly 585 billion years, more than 40 times the age of the universe, which is currently estimated at around 13.8 billion years.
| Discs | Fewest moves | At 1 move/second |
|---|---|---|
| 5 | 31 | 31 seconds |
| 10 | 1,023 | about 17 minutes |
| 20 | 1,048,575 | about 12 days |
| 30 | 1,073,741,823 | about 34 years |
| 40 | 1,099,511,627,775 | about 35,000 years |
Press the solve button and watch the smallest disc. It moves on every other turn, always in the same circular direction around the pegs. On the turns in between, there is only one legal move that does not involve the smallest disc, so you just make it. With an even number of discs the smallest disc steps toward the middle peg first; with an odd number it steps to the far peg. No planning is needed, which is why a computer can solve it with almost no memory.
Hanoi is the classic example of recursion: solving a problem by solving a smaller copy of itself. The program is only a few lines long, yet it produces a sequence that doubles in length with every disc. Short instructions do not mean short running time. When a programmer says an algorithm is "exponential", this puzzle is the picture they have in mind: fine for 10 discs, hopeless for 64.