Surely you have already come across the Towers of Hanoi problem: Wooden disks of different sizes are stacked on three pegs, and initially, all disks are stacked on the same peg sorted by size, with the largest disk at the bottom. The objective is to transfer the entire tower to one of the other pegs, moving only one disk at a time and never putting a larger disk onto a smaller one.
According to an old myth, the monks at an ancient Tibetian monastery have been trying to solve an especially large instance of this problem with 47 disks for thousands of years. Since this requires at least 247
- 1 moves and the monks started out without a strategy, they messed it all up while still following the rules. Now they would like to have the disks stacked up neatly on any arbitrary peg using the minimum number of moves. But they all took a vow which forbids them to move the disks contrary to the rules. They want to know on which peg they should best stack the disks, and the minimum number of moves needed.
Write a program that solves this problem for the monks. Your program should also be able to handle any number N (0 < N <= 100 000) of disks. The numbers involved in the computation can become quite large. Because of that, the monks are only interested in the number of moves modulo 1 000 000.
The following example can be solved in four moves.