Ханойская башня

На стержне надета пирамидка из $n$ дисков разного размера, меньший всегда лежит на большем. Нужно перенести её на другой стержень, пользуясь третьим как запасным.

За один ход берут ровно один диск и кладут его либо на пустой стержень, либо на диск большего размера.

Сколько ходов потребуется, если действовать наилучшим образом?

Одно число $n$ от $1$ до $60$.

Одно число.

Чтобы перенести $n$ дисков, надо перенести $n - 1$ на запасной стержень, переложить самый большой и снова перенести $n - 1$. Отсюда и формула для количества ходов.