# 1+3 Towers of Hanoi

There are four pegs in a row; let's call them A, B, C, and D from left to right. Peg A has a stack of $$n$$ differently sized disks, sorted in size so the smallest disk is at the top. All other pegs are empty. The goal is to move all the disks to peg D, following the rules:

• You can move only one disk at a time.
• Disks can only be moved from the top of a stack to the top of another stack.
• You cannot put a larger disk over a smaller one.
• Once a disk leaves peg A, it cannot be moved back to peg A.
• You can move disks freely between pegs B, C, and D.

Describe an optimal (i.e. minimizing the number of steps) sequence of moves. What are the number of moves for $$n=5$$ and $$n=6$$?

Any solution will at one point have the two largest disks on their own pegs and all the others on the third one (the fourth peg (A) is out once the largest disk has been moved). WLOG we move the two largest disk only once the others have been stacked to their single peg (whatever sequence of moves leads there works regardless of where the two largest disks are). The full sequence of moves is therefore an optimal solution for the n-2 problem + 3 moves to move the two largest disks to their final destination + an optimal solution to the n-2 classic (no fourth peg) problem.

From this we get the recursion formula

$$X_1=1,X_2=3,X_n=X_{n-2}+2+2^{n-2}$$

with solution

$$X_{2m}=2m+\frac {4^m-1} 3,X_{2m+1}=2m+2\times\frac {4^m-1} 3+1$$.

UPDATE

As @PM2Ring points out in the comments there is a prettier way of writing the closed formula:

$$X_n=n+\left \lfloor \frac {2^n} 3 \right \rfloor$$

The first few values are

1,3,5,9,15,27,49,93,179,...

• oeis.org/A340849 Commented Jan 24 at 12:54
• There's a slightly more symmetrical way to write the closed forms. It's surprising that they aren't given on OEIS. sagecell.sagemath.org/… Commented Jan 24 at 22:17
• A340849 has been updated with the Hanoi variant reference and the simplified formulas. Commented Feb 21 at 6:09