Four-Tower Towers of Hanoi#6624
Refer to problem three for a description of the classic three-tower version of the Towers of Hanoi problem.
For this problem, we extend the Towers of Hanoi to have four towers and ask the question: "What are the fewest number of moves to solve the Towers of Hanoi problem for a given if we allow four towers instead of the usual three?" We keep the rules of moving disks from one specified rod to another and do not allow a bigger disk to be put on top of a smaller one. The only difference in this problem is that there are two spare rods instead of just one.
For example, to move disks from rod to rod , one valid sequence is: move disk from to , disk from to , disk from to , disk from to , and disk from to , for a total of moves.
Input consists of one positive integer per line, none greater than . For each value of , compute the fewest number of moves for the four-rod problem. Stop processing at the end of file. (There is no end-of-data flag.)
Output the fewest number of moves for each input case. Follow this exact format: Case, one space, the case number, a colon and one space, and the answer for that case. You may assume the answer will fit in a -bit integer type. Do not print any trailing spaces.
Primer 1