cp's OEIS Frontend

A341581 Number of steps needed to move the largest disk out from a stack of n disks in the Towers of Hanoi exchanging disks puzzle with 3 pegs.

%I A341581 #17 Jun 11 2022 04:16:03
%S A341581 0,1,2,5,10,20,37,70,130,243,450,836,1549,2874,5326,9875,18302,33928,
%T A341581 62885,116566,216058,400483,742314,1375932,2550365,4727266,8762262,
%U A341581 16241395,30104390,55800320,103429237,191712350,355350370,658663363,1220872210,2262960276
%N A341581 Number of steps needed to move the largest disk out from a stack of n disks in the Towers of Hanoi exchanging disks puzzle with 3 pegs.
%C A341581 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 A341581 Stockmeyer et al. determine the shortest solution to the puzzle.  a(n) is their h(n) which is the number of steps to go from n disks on peg X to the largest disk to peg Y and the others remaining on X.  This arises in A341580 to go between subgraph "connection" points.
%H A341581 Kevin Ryde, <a href="/A341581/b341581.txt">Table of n, a(n) for n = 0..700</a>
%H A341581 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) = h(n) in section 3.
%H A341581 <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,-1,2,-2).
%H A341581 <a href="/index/To#Hanoi">Index entries for sequences related to Towers of Hanoi</a>
%F A341581 a(n) = A341579(n-2) + A341580(n-1) + 1, for n>=2. [Stockmeyer et al.]
%F A341581 a(n) = 2*a(n-1) - a(n-3) + 2*a(n-4) - 2*a(n-5).
%F A341581 G.f.: x * (1 + x^2 + x^3) /( (1-x) * (1 - x - x^2 - 2*x^4) ).
%F A341581 G.f.: -1/(1-x) + (1 + x + x^3)/(1 - x - x^2 - 2*x^4).
%e A341581 As a graph where each vertex is a configuration of disks on pegs and each edge is a step (as drawn by Scorer et al.),
%e A341581                 A
%e A341581                / \
%e A341581               *---*         n=3 disks
%e A341581              /     \         A to D
%e A341581             *       *        steps
%e A341581            / \     / \      a(3) = 5
%e A341581           *---B---*---*
%e A341581              /     \
%e A341581         D   /       \   *
%e A341581        / \ /         \ / \
%e A341581       *---C           *---*
%e A341581      /     \         /     \
%e A341581     *       *-------*       *
%e A341581    / \     / \     / \     / \
%e A341581   *---*---*---*   *---*---*---*
%e A341581 The recurrence using A341579 and A341580 is steps A341580(2)=3 from A to B, +1 from B to C, and A341579(1) = 1 from C to D (the whole puzzle solution in an n-2 subgraph).
%o A341581 (PARI) my(p=Mod('x,'x^4-'x^3-'x^2-2)); a(n) = subst(lift(p^(n+2))\'x,'x,2)/2 - 1;
%Y A341581 Cf. A341579, A341580.
%K A341581 nonn,easy
%O A341581 0,3
%A A341581 _Kevin Ryde_, Feb 16 2021