Four-Tower Towers of Hanoi

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 n if we allow four towers instead of the usual three?” We keep the rules of trying to move n disks from one specified post to another and do not allow a bigger disk to be put on top of a smaller one. What is new for this problem is to have two spare posts instead of just one.

For example, to move 3 disks from post A to post D, we can move disk 1 from A to B, disk 2 from A to C, disk 3 from A to D, disk 2 from C to D, and disk 1 from B to D, making a total of 5 moves.

Input Specification

Input will be positive integers (n), one per line, none being larger than 1 000. For each value of n, compute the fewest number of moves for the four-tower problem. Stop processing at the end of the file. (There is no end-of-data flag.)

Output Specification

Output the fewest number of moves. Follow this format exactly: “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 64-bit integer type. Do not print any trailing spaces.

Sample Input

1. 1
2. 3
3. 5

download as text file

Output for Sample Input

1. Case 1: 1
2. Case 2: 5
3. Case 3: 13

download as text file