A001045 (Jacobsthal sequence) and Towers of Hanoi

[wouter meeussen]

 A001045(n)= (absolute) excess clockwise moves (over anti-clockwise) needed
to
 move a tower of size n to the clockwise peg.


Mathematica:
move[1,from_,to_,by_]:={Signature[{from,to,by}]};
(* Signature is +1 if move is clockwise, else -1 *)
move[n_Integer,from_,to_,by_]:=Flatten[{move[n-1,from,by,to],move[1,from,to,
by],move[n-1,by,to,from]}];

Table[Plus@@((move[n,1,2,3])) ,{n,16}]
gives =-(-1)^n*(2^n - (-1)^n)/3
{1,-1,3,-5,11,-21,43,-85,171,-341,683,-1365,2731,-5461,10923,-21845}


The count of all clockwise moves a(n) is
{1,1,5,5,21,21,85,85,341,341,1365,1365,5461,5461,21845,21845}
or A002450( Ceiling[n/2] ) with A002450(n)=(4^n - 1)/3

That of all anti-clockwise moves is (2^n-1)-a(n)
{0,2,2,10,10,42,42,170,170,682,682,2730,2730,10922,10922,43690}
or A020988( Floor[n/2]) with A020988(n)=2*(2^{2n+2} - 1)/3.
A020988 *does* refer to the TowersOfHanoi problem.

cursorily yours,

Wouter Meeussen
wouter.meeussen at pandora.be