a last little remark on the Towers of Hanoi problem

[wouter meeussen]

moving a tower of n disks from peg 1 to 2 (using 3)
gives rise to disk-by-disk move-instructions covering all six permutations
of {1,2,3}.
Coding each {from,to,by}-instruction as the Rank of that permutation,
we obtain
{1,2,3}::0 ; {1,3,2}::1 ; {2,1,3}::2
{2,3,1}::3 ; {3,1,2}::4 ; {3,2,1}::5

If we now count the number of moves 0,..,5 when moving a n-disk tower,
we get:

{1, 0, 0, 0, 0, 0}
{1, 1, 0, 0, 0, 1}
{3, 1, 0, 1, 1, 1}
{3, 4, 2, 1, 1, 4}
{9, 4, 2, 6, 6, 4}
{9, 15, 12, 6, 6, 15}
{31, 15, 12, 27, 27, 15}
{31, 58, 54, 27, 27, 58}
{117, 58, 54, 112, 112, 58}
{117, 229, 224, 112, 112, 229}
{459, 229, 224, 453, 453, 229}
{459, 912, 906, 453, 453, 912}
{1825, 912, 906, 1818, 1818, 912}
{1825, 3643, 3636, 1818, 1818, 3643}
{7287, 3643, 3636, 7279, 7279, 3643}
{7287, 14566, 14558, 7279, 7279, 14566}
{29133, 14566, 14558, 29124, 29124, 14566}

this turns out to be (thanks to SuperSeeker):

Table[{
 (4^(Floor[n/2]+1)+6 Floor[n/2]+5)/9,
((4^(Ceiling[n/2]+1)+6 Ceiling[n/2]+5)/9-1)/2,
((4^(Ceiling[n/2]+1)+6 Ceiling[n/2]+5)/9-1)/2-Ceiling[n/2],
( 4^(Floor[n/2]+1)+6 Floor[n/2]+5)/9-Floor[n/2]-1,
( 4^(Floor[n/2]+1)+6 Floor[n/2]+5)/9-Floor[n/2]-1,
((4^(Ceiling[n/2]+1)+6 Ceiling[n/2]+5)/9-1)/2
      },{n,0,16}]//ColumnForm

and this is a cute way to decompose 2^n-1.

Wouter Meeussen
wouter.meeussen at pandora.be