Move the Stack 2

Suppose we started with $4$ disks (in ascending order) with the top two disks the same on one peg and wanted to move the top $2$ disks over to another peg. This would take a minimum of $2$ moves.

Now suppose we wanted to move the top $3$ over to another peg instead. We would need to move the top $2$ disks over to one peg ( $2$ moves), then move the third disk over to a different peg ( $1$ move), and then move the top $2$ disks again on top of the third disk ( $2$ moves) for a total of $2 + 1 + 2 = 5$ moves.

Now suppose we wanted to move the top $4$ over to another peg instead. We would need to move the top $3$ disks over to one peg ( $5$ moves), then move the fourth disk over to a different peg ( $1$ move), and then move the top $3$ disks again on top of the fourth disk ( $5$ moves) for a total of $5 + 1 + 5 = 11$ moves.

This is a recursive pattern, so that if $a_n$ is the minimum number of moves to move $n$ disks (where the top two are the same and the rest are different in ascending order), then $a_2 = 2$ and $a_n = 2a_{n - 1} + 1$ for $n > 2$ . The first few terms are $2$ , $5$ , $11$ , $23$ , $47$ , $95$ , $191$ and so on, and it can be shown by induction to satisfy $a_n = 3 \cdot 2^{n - 2} - 1$ for $n \geq 1$ .

In this problem, we are almost moving $n = 31$ disks over, except the first move is already given, and we don't need the last move since we only need to end with a stack of $30$ , so the minimum number of moves needed is $a_{31} - 1 - 1 = (3 \cdot 2^{31 - 2} - 1) - 1 - 1 = \boxed{1610612733}$ .