Tower of Hanoi: Why 64 Disks Take 585 Billion Years

Three disks take 7 moves; 64 disks, at one move per second, take about 585 billion years. The Tower of Hanoi, solved with one recursive idea.

Three pegs, a stack of disks and two rules: move one disk at a time, and never put a larger disk on a smaller one. Three disks take 7 moves; 64 disks, at one move per second, take about 585 billion years.

This video solves the Tower of Hanoi with a three-step recursive idea, walks through the pseudocode and its call tree, proves that 2ⁿ − 1 moves are both enough and necessary, and ends with a pattern that lets you solve any tower by hand without recursion.

In this video

Small towers by hand
The recursive idea
Counting the moves
Why there is no shortcut
Doubling with every disk
A pattern you can follow by hand

Details

Length: 9:29
Language: English, with English captions
Production: Written, animated and narrated by an AI system; synthetic voice