cp's OEIS Frontend

A341583 Geometric length of the solution to the Towers of Hanoi exchanging disks puzzle with 3 pegs and n disks.

%I A341583 #15 Jul 15 2023 06:21:12
%S A341583 0,1,3,8,18,42,94,208,450,966,2052,4330,9074,18920,39266,81182,167268,
%T A341583 343634,704122,1439496,2936906,5981174,12161332,24691514,50066690,
%U A341583 101400616,205150098,414653998,837377988,1689714242,3407154474,6865700808,13826659450,27829885126
%N A341583 Geometric length of the solution to the Towers of Hanoi exchanging disks puzzle with 3 pegs and n disks.
%C A341583 Scorer, Grundy and Smith define a variation of the Towers of Hanoi puzzle where the smallest disk moves freely and two disks can exchange positions when they differ in size by 1, are on different pegs, and each is topmost on its peg.  The puzzle is to move a stack of n disks from one peg to another.
%C A341583 Stockmeyer et al. determine the shortest solution to the puzzle.  a(n) is their d(n) which is the geometric length of the solution when the state graph is embedded in a grid of unit triangles in the manner of the sample drawing by Scorer et al.
%C A341583 Graph n comprises 3 copies of graph n-1.  The embedding arranges these 3 copies as a large triangle with a unit gap between the corners.  The edges connecting these subgraphs are in the middle of the inner sides.  A move of the smallest disk is length 1.  An exchange of disks s and s+1 is length 2^s, where the smallest disk is s=0.
%H A341583 Kevin Ryde, <a href="/A341583/b341583.txt">Table of n, a(n) for n = 0..700</a>
%H A341583 Paul K. Stockmeyer et al., <a href="https://doi.org/10.1080/00207169508804452">Exchanging Disks in the Tower of Hanoi</a>, International Journal of Computer Mathematics, volume 59, number 1-2, pages 37-47, 1995.  Also <a href="http://www.cs.wm.edu/~pkstoc/gov.pdf">author's copy</a>.  a(n) = d(n) in section 5 exercise 5.
%H A341583 <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (3,-1,-2,2,-4).
%H A341583 <a href="/index/To#Hanoi">Index entries for sequences related to Towers of Hanoi</a>
%F A341583 a(n) = (7*2^n - A341579(n+3) + A341579(n))/2.
%F A341583 a(n) = 3*a(n-1) - a(n-2) - 2*a(n-3) + 2*a(n-4) - 4*a(n-5).
%F A341583 G.f.: x * (1 - x) * (1 + x + x^2) / ( (1 - 2*x) * (1 - x - x^2 - 2*x^4) ).
%F A341583 G.f.: (7/2)/(1 - 2*x) - (1/2)*(7 + 5*x + 3*x^2 + 6*x^3)/(1 - x - x^2 - 2*x^4).
%e A341583 The graph embedding in a triangular grid is (as drawn by Scorer et al.),
%e A341583                 A
%e A341583                / \              n=3 disks
%e A341583               *---*              A to D
%e A341583              /     \            geometric
%e A341583             *       *         length along
%e A341583            / \     / \          the path
%e A341583           *---B---*---*         a(3) = 8
%e A341583              /     \
%e A341583         *   .       \   *
%e A341583        / \ /         \ / \
%e A341583       *---C           *---*
%e A341583      /     \         /     \
%e A341583     *       *-------*       *
%e A341583    / \     / \     / \     / \
%e A341583   D---*---*---*   *---*---*---*
%e A341583 B to C is where disks s=1 and s+1=2 exchange which is geometric length 2^s = 2.
%t A341583 A341583list[nmax_]:=LinearRecurrence[{3,-1,-2,2,-4},{0,1,3,8,18},nmax+1];A341583list[50] (* _Paolo Xausa_, Jun 29 2023 *)
%o A341583 (PARI) my(p=Mod('x,'x^4-'x^3-'x^2-2), f=7*'x^3+5*'x^2+3*'x+6); a(n) = (7<<n - polcoeff(lift(f*p^n),3))/2;
%Y A341583 Cf. A341579.
%K A341583 nonn,easy
%O A341583 0,3
%A A341583 _Kevin Ryde_, Feb 16 2021