Calculate
Tower of Hanoi Calculator
How many moves does a perfect game take? Enter a number of disks and find out — plus how long that would actually take to play.
Minimum moves
Expert — playable on the board
On this page
How long that really is
The counts above are exact, and on their own they teach almost nothing — past a few billion, one very large number looks much like another. What the arithmetic is really doing is easier to see than to say. Because every extra disk doubles the work, a ruler with evenly spaced disks is a ruler with multiplying spans of time, and the whole distance from a coffee break (ten disks, seventeen minutes) to the age of the universe (fifty-nine disks) turns out to be about fifty steps.
- 1 disk — 1 move — 1 second: the first size that reaches a second.
- 6 disks — 63 moves — 1 minute: the first size that reaches a minute.
- 12 disks — 4,095 moves — 1 hour: the first size that reaches an hour.
- 17 disks — 131,071 moves — 1 day: the first size that reaches a day.
- 25 disks — 33,554,431 moves — 1 years: the first size that reaches a year.
- 32 disks — 4,294,967,295 moves — 136 years: the first size that reaches a human lifetime.
- 38 disks — 274,877,906,943 moves — 8.71 thousand years: the first size that reaches all of recorded history.
- 59 disks — 576,460,752,303,423,487 moves — 18.3 billion years: the first size that reaches the age of the universe.
The shaded stretch near the left is everything you can actually play here. Eleven disks is a long sitting; twenty-five is a year of uninterrupted moves; fifty-nine passes the age of the universe. Nothing about the rules changes anywhere along that axis — only the count does.
The formula
A perfect game of n disks takes exactly 2ⁿ − 1 moves — the Tower of Hanoi formula, usually typed as 2^n − 1 where superscripts are not to hand. That is not the best anyone has managed — it is a proven floor. To move the largest disk at all, every smaller disk has to be stacked out of the way on the spare tower, and once the largest has crossed they all have to come back on top of it. Two full transfers of n − 1 disks, plus one move:
T(n) = 2·T(n − 1) + 1, starting from T(0) = 0 — no disks, no moves.
Move the n−1 disks above it onto the spare tower. Nothing else can happen until they are out of the way.
The largest disk is free now, and its target is empty. It crosses in a single move — the only move this phase needs.
Rebuild the n−1 stack on top of it. That is the same problem again with one fewer disk, all the way down to a single disk that moves in one step.
Unrolling that gives 1, 3, 7, 15, 31, 63 — each one double the last plus one, which is the sequence of numbers one below a power of two. Every disk you add slightly more than doubles the work, which is why the puzzle goes from a coffee break to longer than the universe has existed in under fifty steps.
The same recurrence is where the puzzle's reputation in a computer science course comes from. Because the work doubles with each disk, the recursive solution runs in O(2ⁿ) time — there is no cleverer algorithm hiding behind that, since the move count itself is exponential and every move has to be printed. What it does not cost is memory: the recursion only ever descends one disk at a time, so it holds O(n) stack frames — one per disk plus one for the base case: sixteen for the largest board here, sixty-five for the legend. The full derivation, and why this is not a recurrence the Master Theorem applies to, is on the Tower of Hanoi algorithm page.
Minimum moves by disk count
These are the sizes you can play here. The difficulty band is the one the board shows beside the disk stepper, and every disk count links to the move list that solves it.
| Disks | Minimum moves | At 1 move/second | Difficulty |
|---|---|---|---|
| 3 | 7 | 7 seconds | Easy |
| 4 | 15 | 15 seconds | Easy |
| 5 | 31 | 31 seconds | Medium |
| 6 | 63 | 1 minute | Medium |
| 7 | 127 | 2 minutes | Hard |
| 8 | 255 | 4 minutes | Hard |
| 9 | 511 | 8 minutes | Expert |
| 10 | 1,023 | 17 minutes | Expert |
| 11 | 2,047 | 34 minutes | Expert |
| 12 | 4,095 | 1 hour | Legend |
| 13 | 8,191 | 2 hours | Legend |
| 14 | 16,383 | 4 hours | Legend |
| 15 | 32,767 | 9 hours | Legend |
Beyond the board
Past 15 disks the puzzle stops being something you play and becomes something you calculate. The counts are still exact — they are just no longer reachable in a human lifetime.
| Disks | Minimum moves | At 1 move/second |
|---|---|---|
| 16 | 65,535 | 18 hours |
| 20 | 1,048,575 | 12 days |
| 25 | 33,554,431 | 1 years |
| 30 | 1,073,741,823 | 34 years |
| 40 | 1,099,511,627,775 | 34.8 thousand years |
| 50 | 1,125,899,906,842,623 | 35.7 million years |
| 64 | 18,446,744,073,709,551,615 | 585 billion years |
These numbers have a name
A number one below a power of two is a Mersenne number, written Mn = 2n − 1 — so every figure in the tables above is one, and the move count of a Tower of Hanoi game is never anything else. When a Mersenne number happens to be prime it is a Mersenne prime, and those are the numbers the search for record-breaking primes has run on for decades, because 2n − 1 is far cheaper to test for primality than an arbitrary number its size.
Mn can only be prime when n itself is prime, but that is not enough on its own — and the counterexample is a game you can play here. Eleven is prime; its 2,047 moves are not, since 2,047 = 23 × 89. Of the sizes on this board, 3, 5, 7 and 13 disks are the ones whose move counts are prime. OEIS A000225 is the full sequence.
The sixty-four disk legend
The puzzle went on sale in 1883, and within a year it had a story: in a temple in Benares, priests are moving sixty-four golden disks between three diamond needles, and when the last disk is placed the world ends. The arithmetic is reassuring. Sixty-four disks take 18,446,744,073,709,551,615 moves, and at one move per second that is 585 billion years — some forty times the current age of the universe.
Frequently asked questions
How many moves does Tower of Hanoi take?
The minimum is 2ⁿ − 1 moves for n disks. Three disks take 7 moves, five take 31, ten take 1,023, and twenty take 1,048,575. Every extra disk slightly more than doubles the total, because solving n disks means solving n − 1 disks twice with one move in between.
Why is the formula 2ⁿ − 1?
To move n disks you must first move the top n − 1 out of the way, then move the largest disk once, then move those n − 1 back on top of it. That gives T(n) = 2·T(n−1) + 1 with T(1) = 1, and unrolling it gives 1, 3, 7, 15, 31 — each one double the last plus one, which is exactly 2ⁿ − 1.
What is the time complexity of Tower of Hanoi?
O(2ⁿ). Each disk doubles the work, so the recursive solution makes 2ⁿ − 1 moves, and no algorithm can beat that — the moves themselves have to be produced, and there are that many of them. Space is only O(n): the recursion descends one disk at a time, so it holds at most n + 1 stack frames at once, which is why a 64-disk call would exhaust your patience long before it exhausted the stack.
How long would 64 disks take?
Sixty-four disks need 18,446,744,073,709,551,615 moves. At one move per second that is 585 billion years — far longer than the current age of the universe, which is the point of the legend that was attached to the puzzle in 1884.
Can a solution ever be shorter than 2ⁿ − 1?
No. 2ⁿ − 1 is a proven lower bound, not a best-known result: the largest disk has to move at least once, and before it can, every smaller disk must be off it and off its destination. That forces the two sub-transfers, and the argument repeats all the way down.
Does the calculator work for a partly solved board?
Not this page — 2ⁿ − 1 assumes every disk starts on one tower. For the shortest solution from a position that is already part-way there, use the solver, which computes the optimal path from any legal arrangement.