Tower of Hanoi

Legend says a temple in Benares, India holds three pegs where monks move 64 golden disks from one peg to another, day and night. The day they finish, the world ends. Scary? Once you see how the move counts grow, you will know how far away that "doomsday" really is.

Only three rules

The goal: carry a whole stack of disks from the left peg to the right peg.

Move one disk at a time, and only the topmost disk of a peg;
A disk can only sit on top of a peg;
A larger disk may never rest on a smaller one.

The rules are simple, but the third one is a landmine: place one big disk on a small one and the attempt is ruined on the spot. By the way, the smallest disk is the freest — it may rest on anything, and never breaks a rule.

Cracking three disks

Thinking about three disks all at once gets tangled. The trick: master two disks, and three disks follow.

To move 3 disks onto the target peg:

First move the top 2 disks onto the middle spare peg (3 moves);
Move the biggest disk straight onto the target peg (1 move);
Move the 2 disks from the spare peg back on top of it (3 moves).

$3 + 1 + 3 = 7$ moves, done. Notice anything? "Moving 2 disks" happened twice — the big job split into two smaller jobs plus one move of its own.

Four disks work the same way: move 3 disks to the spare peg (7 moves), shift the biggest disk (1 move), move the 3 disks back on top (7 moves) — 15 in total. If you can move n−1 disks, you can move n. There is no end to this road, and it always works.

InteractiveTower of Hanoi

Disks

Moves: 0Minimum: 7

Move one disk at a time; never place a larger disk on a smaller one

The move count: 1, 3, 7, 15, 31…

Count the minimum moves:

Disks	1	2	3	4	5
Minimum moves	1	3	7	15	31

The pattern is double, then add 1: $3 = 1 \times 2 + 1$ , $7 = 3 \times 2 + 1$ , $15 = 7 \times 2 + 1$ … written as a formula:

$2^n - 1$

For n disks, the minimum is $2^n - 1$ moves. This matches the strategy exactly: moving n disks = moving n−1 disks twice + moving the big disk once.

Why 64 disks never finish

Do the math

$2^{64} - 1 \approx 1.8 \times 10^{19}$ . Even at one disk per second, without stopping, the monks would need about 585 billion years — more than 40 times the age of the universe (roughly 14 billion years). The world is safe.

That is the scary side of exponential growth: adding one disk is a tiny step, yet the move count nearly doubles. Going from 5 disks to 10 raises the minimum from 31 to 1023 — still only about 17 minutes at one move per second, no problem at all; at 20 disks it passes a million moves. Anything that doubles at every step very soon becomes unimaginable.

Check yourself

Quick quiz

1. What is the minimum number of moves for 3 disks?
2. Going from 3 disks to 4, the minimum rises from 7 to what?
3. Why will the 64-disk legend never be finished?