With n disks, the fewest moves needed to move the tower to another pole in the Tower of Hanoi is 2ⁿ − 1. It is the number you get by multiplying 2 by itself as many times as there are disks, and subtracting 1.

Number of disksFewest moves
1 disk1
2 disks3
3 disks7
4 disks15
5 disks31
6 disks63
7 disks127
8 disks255
9 disks511

Every time you add a disk, the number of moves roughly doubles. Let’s see why, step by step.

Focus on the Largest Disk

Think about moving a tower of n disks from the left to the right. The largest disk is under the other disks, so you cannot move it as it is. To carry the largest disk to the right, the following must be true at that moment:

  • Nothing is on top of the largest disk.
  • The right pole is empty (because a smaller disk cannot be placed under the largest disk).

In other words, the other n − 1 disks must all be stacked on the middle pole.

Split the Moves into Three Parts

From here, the moves for n disks can be split into three parts:

  1. Move the top n − 1 disks from the left to the middle.
  2. Move the largest disk from the left to the right in one move.
  3. Move the n − 1 disks in the middle onto the largest disk.

Parts 1 and 3 are both exactly the problem “move a tower of n − 1 disks”. If we write the fewest moves for n disks as T(n), then

T(n) = T(n − 1) + 1 + T(n − 1) = 2 × T(n − 1) + 1

holds. With 1 disk it is 1 move, so T(1) = 1. From there you can find, in order, 3, 7, 15, 31…

Why the Formula Is 2ⁿ − 1

If you add 1 to both sides of this relation, you get

T(n) + 1 = 2 × (T(n − 1) + 1).

It means that “the number of moves plus 1” exactly doubles every time you add a disk. With 1 disk, T(1) + 1 = 2, so with n disks it is 2 multiplied n times, 2ⁿ. Subtract 1 from that, and T(n) = 2ⁿ − 1.

Why You Cannot Do It in Fewer Moves

We have seen that the tower can be moved in 2ⁿ − 1 moves with the steps above. But is there not a way to move it in fewer?

As we saw, at the moment you first move the largest disk, the other n − 1 disks must all be stacked on one other pole. Getting there takes at least the moves needed to move a tower of n − 1 disks. In the same way, after you place the largest disk on the right for the last time, stacking the other n − 1 disks back on top of it also takes at least the moves needed to move a tower of n − 1 disks. The largest disk itself also moves at least once.

Whatever the solution, these three amounts of moves are always needed. So you cannot do it in fewer than 2 × T(n − 1) + 1 moves. It is also known that there is actually only one solution with the fewest moves.

The App’s “Classic” Mode Is 127 Moves

The Classic mode in the Tower of Hanoi app uses 7 disks, so the fewest moves is 2⁷ − 1 = 127. When the move count is 127, you have solved it in the fewest moves. If you move the small disk in the same direction, as introduced in the article on how to play, you finish in exactly 127 moves.