a In the original version of the Tower of Hanoi puzzle as it

a. In the original version of the Tower of Hanoi puzzle, as it was published
by Edouard Lucas, a French mathematician, in the 1890s, the world will
end after 64 disks have been moved from a mystical Tower of Brahma.
Estimate the number of years it will take if monks could move one disk
per minute. (Assume that monks do not eat, sleep, or die.)
b. How many moves are made by the ith largest disk (1 i n) in
this algorithm?
c. Design a nonrecursive algorithm for the Tower of Hanoi puzzle.

Solution

Towers of Hanoi problem is about moving n disks from one peg to another using another auxiliary peg.

And to move a total of n disks it takes a total of 2ⁿ - 1 moves.

So, to move 1 disk it requires 2 - 1 = 1 move.

So, to move 2 disk it requires 4 - 1 = 3 move.

So, to move 3 disk it requires 8 - 1 = 7 move.

And so on.....

To move 64 disks it requires 2⁶⁴ - 1 = 1.84 e 19 moves in total.

b. The number of moves made by the largest disk in the pile is 1. And the number of moves made by the next largest disk is 2, and next largest disk is 4. And the series goes like... 8, 16, 32, ....

And to move i^th largest disk it takes a total of 2^i-1.