The Tower of Hanoi comes with a legend. In a temple in India, there is a tower of 64 golden disks, and monks keep moving the disks according to the rules. When they have moved them all, the world will end.
So how long would it really take to move 64 disks?
At Least 2⁶⁴ − 1 Moves
With n disks, the fewest moves is 2ⁿ − 1. (The reason is explained in the article on the minimum number of moves.) With 64 disks, that is
2⁶⁴ − 1 = 18,446,744,073,709,551,615 moves.
That is about 18.4 quintillion moves. In Japanese counting units, it is about 1,845 kei, where one kei is 10,000 trillion. It is 18.45 million times one trillion.
At One Move per Second
Suppose a monk moves one disk per second without ever resting or making a single mistake. Taking a year as about 31.56 million seconds (365.25 days), you divide:
18,446,744,073,709,551,615 seconds ÷ 31,557,600 seconds ≒ 584.5 billion years
That is how long it would take.
| Compared with | Years |
|---|---|
| Moving 64 disks at one move per second | About 584.5 billion years |
| From the birth of the universe until now | About 13.8 billion years |
| From the birth of the Earth until now | About 4.6 billion years |
That is about 42 times the age of the universe. Even if the legend were true, there is no need to worry about the end of the world.
What About a Computer?
Suppose a computer that can calculate a billion moves per second follows the solution, instead of a person’s hands. It would still take
18,446,744,073,709,551,615 ÷ 1,000,000,000 ≒ 18.4 billion seconds ≒ about 585 years.
Each individual step is very simple, yet as the number of disks grows, the number of moves doubles again and again. It is a clear example of what “growing exponentially” means.
How Many Disks Can You Play by Hand?
At one move per second, even with the fewest moves, it takes this long.
| Number of disks | Fewest moves | At one move per second |
|---|---|---|
| 7 disks | 127 moves | About 2 minutes |
| 10 disks | 1,023 moves | About 17 minutes |
| 15 disks | 32,767 moves | About 9 hours |
| 20 disks | 1,048,575 moves | About 12 days |
For a quick break, around 7 disks is just the right length. That is also why the Classic mode in the Tower of Hanoi app uses 7 disks.
