The Tower of Hanoi asks you to move a stack of n disks from a source peg to a target peg, one disk at a time, never placing a larger disk on a smaller one.

The recursive idea

To move n disks from A to C using spare peg B:

• Move the top n−1 disks from A to B (recursively).
• Move the largest disk from A to C.
• Move the n−1 disks from B to C (recursively).

Why 2ⁿ−1 moves

The move count satisfies T(n) = 2·T(n−1) + 1 with T(0) = 0. Unrolling the recurrence gives the closed form T(n) = 2ⁿ − 1. This is the proven minimum — no shorter solution exists.

Binary & Gray-code connection

Number the moves 1, 2, 3, … in binary. On move k the disk being moved is the position of the lowest set bit of k (disk 1 = smallest). The sequence of disk states traces a Gray code: each move flips exactly one disk, so consecutive states differ in one "digit", just like reflected binary Gray code.

The legend

In the temple legend, priests move 64 golden disks; the world ends when they finish. At one move per second that takes 2⁶⁴ − 1 ≈ 5.85 × 10¹¹ years — far longer than the age of the universe.

More pegs (Frame–Stewart)

With 4 or more pegs the optimal count drops sharply. The Frame–Stewart algorithm splits the stack and is conjectured optimal, but this simulation keeps the classic 3-peg core where 2ⁿ − 1 is exact.