The legend of 64 golden disks — finish moving them, and the world ends.
Three pegs, disks of different sizes. You may move one disk at a time, and a larger disk can never sit on a smaller one. What is the fewest moves to shift a 3-disk tower to another peg?
The Tower of Hanoi is not a moving problem — it is a splitting problem.
Experiment
Hands-on experiment
Rules: one disk at a time · a larger disk never sits on a smaller one. Tap a peg to pick up its top disk, tap another peg to drop it.
Tap a peg to pick up its top disk.
📖 Read more — why it exists · insights · common mistakes · formulasExpand ▾
Why
Why does this exist?
The Tower of Hanoi was invented in 1883 by the French mathematician Édouard Lucas. The tale of Brahmin priests moving 64 golden disks — 'when they finish, the world ends' — was a legend Lucas made up to package the puzzle.
The puzzle has survived 140+ years not for its answer but for its method. There is no way to move n disks at once. But the moment you think 'first clear the n−1 disks above', the big problem becomes the same problem one size smaller.
Thinking that splits a problem into a smaller copy of itself is called recursion. It is the backbone of how computers sort and search huge data. The Tower of Hanoi is the oldest hands-on lab for recursion.
Insight
Insights from the video
“You don't need to know how to move n disks — only n−1.”
Clear the top n−1 disks to the spare peg, move the bottom disk, and stack the n−1 back on. Instead of solving the big problem, you delegate to a smaller one. That delegation is all recursion is.
“When doubling repeats, human intuition always loses.”
Double per disk: ten disks is a thousand moves, twenty is a million, and 64 is 40 times the age of the universe. Only someone who has felt exponential explosion avoids the 'it'll be quick' trap.
Misconception
Common misconceptions
One more disk means just a few more moves.
It grows by multiplication, not addition. Each extra disk roughly doubles the minimum, because the n−1 disks above must be moved twice. Three disks take 7 moves; ten disks already take 1,023.
64 disks? Just move fast and it's done.
At one move per second, nonstop, it takes about 585 billion years — over 40 times the age of the universe (about 13.8 billion years). Diligence cannot beat an exponential.
Formula
Writing it as math
Let's translate what you discovered into symbols. Call the minimum for n disks M(n); the clear-move-restack routine your hands just performed becomes the formula itself.
🔬 Formula anatomy — the three hand motions become the equation
= + +
Recurrence (the split)
The answer for n is twice the answer for n−1, plus one. This is the moment the big problem splits into a smaller one.
Closed form
Unroll the recurrence all the way and this single line remains. 1, 3, 7, 15, 31, … each one less than a power of two.
The time for 64 disks
Even at one move per second, that is over 40 times the age of the universe. That is why the legend says the world ends.
In Real Life
Where you meet it in real life
Divide-and-conquer algorithms
To sort a million records, a computer splits them in half again and again, sorts the small pieces, and merges (merge sort). It is exactly the Hanoi habit of delegating to a smaller copy of the problem.
Every programmer's first recursion
The Tower of Hanoi is the classic first example when programming courses teach recursive functions, because it shows a function calling itself in a way you can watch.
Backup tape rotation
A classic scheme for rotating server backups is literally called the 'Tower of Hanoi' rotation. It borrows the disks' rhythm — disk 1 moves every 2nd turn, disk 2 every 4th.
Problem-solving research in psychology
Cognitive psychology and neuroscience use the Tower of Hanoi to measure planning ability, because it exposes how far ahead a person can set intermediate goals.
Practice
Practice — conquer the types
✏️ 4 practice problems — solve to conquerTap to solve ▾
What is the minimum number of moves for 4 disks?
Why is the minimum M(n) = 2M(n−1) + 1?
What is the minimum number of moves for 5 disks?
When one more disk is added, the minimum number of moves…
Watch
Related video
Connection
Concepts connect
Previous concept
Exponentiation
Feel how fast repeated doubling grows first, and the weight of 2ⁿ − 1 becomes visible.
← Exponentiation labLeads to next
The Hundred Doors
Next problem — which doors stay open after 100 people toggle them? This time divisors take the stage.
Go to the The Hundred Doors lab →Related
Labs worth exploring together
Related lab
Sequences
Recurrences like M(n) = 2M(n−1) + 1 — the grammar of building each term from the last lives here.
Go to the Sequences lab →Related lab
The Chessboard & Rice
Doubling per square — the same 2ⁿ explosion that bankrupted a king.
Go to the The Chessboard & Rice lab →