The Tower of Hanoi Formula: How Many Moves Does It Take? (2^n - 1)
Tower of Hanoi guide · 5 min read
If you've ever wondered how many moves the Tower of Hanoi actually takes, there's a clean answer. The Tower of Hanoi formula is 2ⁿ − 1, where n is the number of disks. That single expression tells you the minimum number of moves for any size of the puzzle, and it hides one of the most striking facts in recreational math: a 64-disk tower would take longer to solve than the universe has existed. This guide explains the formula, the move counts for each disk count, and why 2ⁿ − 1 is the best you can ever do. New to the puzzle? Start with how to solve the Tower of Hanoi.
The formula and what it means
The minimum number of moves to solve a Tower of Hanoi with n disks is:
2ⁿ − 1
"Minimum" matters here. You can always solve it in more moves by making mistakes, but you can never solve it in fewer than 2ⁿ − 1. A perfect solver hits that number exactly every time.
Moves for each disk count
Because the formula doubles with each added disk, the move count grows fast:
| Disks (n) | Formula | Minimum moves |
|---|---|---|
| 1 | 2¹ − 1 | 1 |
| 2 | 2² − 1 | 3 |
| 3 | 2³ − 1 | 7 |
| 4 | 2⁴ − 1 | 15 |
| 5 | 2⁵ − 1 | 31 |
| 6 | 2⁶ − 1 | 63 |
| 7 | 2⁷ − 1 | 127 |
| 8 | 2⁸ − 1 | 255 |
| 9 | 2⁹ − 1 | 511 |
| 10 | 2¹⁰ − 1 | 1,023 |
This is exactly why our difficulty levels feel the way they do. The easy 3-disk puzzle is a quick 7 moves, while the Einstein 10-disk level demands 1,023. The thinking is identical; only the move count explodes.
Why the formula works
You don't need heavy math to see where 2ⁿ − 1 comes from. Think about what it takes to solve n disks, building on the solution for n − 1 disks:
- Move the top n − 1 disks to the spare peg. That takes however many moves n − 1 disks need, call it M(n − 1).
- Move the single biggest disk to the goal. That's 1 move.
- Move the n − 1 disks back on top. Another M(n − 1) moves.
So the moves for n disks are:
M(n) = 2 × M(n − 1) + 1
Starting from M(1) = 1, this doubles and adds one each step: 1, 3, 7, 15, 31, and so on. Work the pattern through and it collapses neatly into the closed form M(n) = 2ⁿ − 1. The recursive structure of the puzzle, explained in the Tower of Hanoi algorithm, is the reason the count behaves this way.
The legend: 64 disks and the end of the world
The formula is also the heart of the puzzle's famous legend, the Tower of Brahma. As the story goes, priests in a temple are moving a tower of 64 golden disks, and when they place the final disk, the world ends. So how long would that take?
Plug n = 64 into the formula:
2⁶⁴ − 1 = 18,446,744,073,709,551,615 moves
That's about 18.4 quintillion moves. Even at a brisk one move per second, finishing would take roughly 585 billion years, far longer than the current age of the universe. The world is safe for a while. We tell the full story in the legend and history of the Tower of Hanoi.
The binary connection
There's a lovely bonus hiding in the numbers. Write 2ⁿ − 1 in binary and you get a string of n ones: 7 is 111, 15 is 1111, 31 is 11111. In fact, each move in the optimal solution corresponds to counting up in binary, where the bit that flips tells you which disk to move. The Tower of Hanoi is secretly a binary counter, which is part of why it fascinates mathematicians and computer scientists alike.
What the formula tells a solver
Practically, the formula gives you a target. If you're solving 5 disks and you finish in 31 moves, you solved it optimally. Finish in 40 and you took some detours. Many players use the move counter on our puzzles to chase that perfect 2ⁿ − 1 score, which turns even the deterministic puzzle into a small personal challenge.
Want to test the formula yourself? Pick a difficulty, count your moves, and see how close you get to 2ⁿ − 1. Then watch the auto-solver hit it exactly.
Frequently asked questions
What is the formula for the Tower of Hanoi?
The minimum number of moves is 2ⁿ − 1, where n is the number of disks. For example, 3 disks need 2³ − 1 = 7 moves, and 4 disks need 2⁴ − 1 = 15 moves. It's impossible to solve the puzzle in fewer moves.
How many moves does the Tower of Hanoi take with 64 disks?
A 64-disk tower takes 2⁶⁴ − 1 moves, which is 18,446,744,073,709,551,615 moves (about 18.4 quintillion). At one move per second that would take roughly 585 billion years, the basis of the puzzle's end-of-the-world legend.
Why is the Tower of Hanoi 2 to the power of n minus 1?
Because solving n disks means solving n − 1 disks twice (move them aside, then move them back) plus one move for the biggest disk. That gives M(n) = 2 × M(n − 1) + 1, which works out to the closed form 2ⁿ − 1.
What is the minimum number of moves for 5 disks?
Five disks take 2⁵ − 1 = 31 moves. If you solve our hard 5-disk puzzle in 31 moves, you've found the optimal solution.