cp's OEIS Frontend

A341580 Number of steps needed to reach position "YZ^(n-1)" in the Towers of Hanoi exchanging disks puzzle with 3 pegs and n disks.

%I A341580 #21 Jun 11 2022 04:16:38
%S A341580 0,1,3,6,12,23,44,82,153,284,528,979,1816,3366,6241,11568,21444,39747,
%T A341580 73676,136562,253129,469188,869672,1611987,2987920,5538286,10265553,
%U A341580 19027816,35269212,65373603,121173924,224603162,416315513,771665884,1430329248,2651201459
%N A341580 Number of steps needed to reach position "YZ^(n-1)" in the Towers of Hanoi exchanging disks puzzle with 3 pegs and n disks.
%C A341580 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 A341580 Stockmeyer et al. determine the shortest solution to the puzzle (A341579).  a(n) is their g(n) which is the number of steps to go from n disks on peg X to the largest on peg Y and the rest on peg Z, denoted "YZ^(n-1)".  This is halfway to the solution for n+1 disks since it allows disk n+1 on X to exchange with disk n on Y.
%H A341580 Kevin Ryde, <a href="/A341580/b341580.txt">Table of n, a(n) for n = 0..700</a>
%H A341580 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) = g(n) in section 3.
%H A341580 <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,-1,2,-2).
%H A341580 <a href="/index/To#Hanoi">Index entries for sequences related to Towers of Hanoi</a>
%F A341580 a(n) = a(n-1) + A341581(n-1) + 1, for n>=1. [Stockmeyer et al.]
%F A341580 a(n) = 2*a(n-1) - a(n-3) + 2*a(n-4) - 2*a(n-5).
%F A341580 G.f.: x * (1 + x + x^3) /( (1-x) * (1 - x - x^2 - 2*x^4) ).
%F A341580 G.f.: -1/(1-x) + (1 + x + x^2 + x^3)/(1 - x - x^2 - 2*x^4).
%e A341580 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 A341580                 A           \
%e A341580                / \          |  n=2 disks
%e A341580               *---*         |  A to B
%e A341580              /     \        |  steps
%e A341580             *       *       |  a(2) = 3
%e A341580            / \     / \      |
%e A341580           *---B---*---*     /
%e A341580              /     \
%e A341580         *   /       \   *        n=3 disks
%e A341580        / \ /         \ / \       A to D
%e A341580       *---C           *---*      steps
%e A341580      /     \         /     \     a(3) = 6
%e A341580     *       *-------*       *
%e A341580    / \     / \     / \     / \
%e A341580   *---*---*---D   *---*---*---*
%e A341580 For n=3, the recurrence using A341581 is a(2)=3 from A to B, A341581(2)=2 from D to C, and +1 from B to C.
%t A341580 CoefficientList[Series[x (1+x+x^3)/((1-x)(1-x-x^2-2x^4)),{x,0,40}],x] (* or *) LinearRecurrence[{2,0,-1,2,-2},{0,1,3,6,12},40] (* _Harvey P. Dale_, Aug 26 2021 *)
%o A341580 (PARI) my(p=Mod('x,'x^4-'x^3-'x^2-2)); a(n) = subst(lift(p^(n+1)),'x,2)/2 - 1;
%Y A341580 Cf. A341579, A341581.
%K A341580 nonn,easy
%O A341580 0,3
%A A341580 _Kevin Ryde_, Feb 16 2021