The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 4
 0, 1, 3, 6, 12, 23, 44, 82, 153, 284, 528, 979, 1816, 3366, 6241, 11568, 21444, 39747, 73676, 136562, 253129, 469188, 869672, 1611987, 2987920, 5538286, 10265553, 19027816, 35269212, 65373603, 121173924, 224603162, 416315513, 771665884, 1430329248, 2651201459 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS 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 top-most on its peg.  The puzzle is to move a stack of n disks from one peg to another. 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. LINKS Kevin Ryde, Table of n, a(n) for n = 0..700 Paul K. Stockmeyer et al., Exchanging Disks in the Tower of Hanoi, International Journal of Computer Mathematics, volume 59, number 1-2, pages 37-47, 1995.  Also author's copy.  a(n) = g(n) in section 3. Index entries for linear recurrences with constant coefficients, signature (2,0,-1,2,-2). FORMULA a(n) = a(n-1) + A341581(n-1) + 1, for n>=1. [Stockmeyer et al.] a(n) = 2*a(n-1) - a(n-3) + 2*a(n-4) - 2*a(n-5). G.f.: x * (1 + x + x^3) /( (1-x) * (1 - x - x^2 - 2*x^4) ). G.f.: -1/(1-x) + (1 + x + x^2 + x^3)/(1 - x - x^2 - 2*x^4). EXAMPLE 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.),                 A           \                / \          |  n=2 disks               *---*         |  A to B              /     \        |  steps             *       *       |  a(2) = 3            / \     / \      |           *---B---*---*     /              /     \         *   /       \   *        n=3 disks        / \ /         \ / \       A to D       *---C           *---*      steps      /     \         /     \     a(3) = 6     *       *-------*       *    / \     / \     / \     / \   *---*---*---D   *---*---*---* 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. PROG (PARI) my(p=Mod('x, 'x^4-'x^3-'x^2-2)); a(n) = subst(lift(p^(n+1)), 'x, 2)/2 - 1; CROSSREFS Cf. A341579, A341581. Sequence in context: A089068 A018180 A079735 * A050243 A285262 A024505 Adjacent sequences:  A341577 A341578 A341579 * A341581 A341582 A341583 KEYWORD nonn,easy AUTHOR Kevin Ryde, Feb 16 2021 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 13 05:21 EDT 2021. Contains 344981 sequences. (Running on oeis4.)