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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 2
0, 1, 2, 5, 10, 20, 37, 70, 130, 243, 450, 836, 1549, 2874, 5326, 9875, 18302, 33928, 62885, 116566, 216058, 400483, 742314, 1375932, 2550365, 4727266, 8762262, 16241395, 30104390, 55800320, 103429237, 191712350, 355350370, 658663363, 1220872210, 2262960276 (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.  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.

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) = h(n) in section 3.

Index entries for linear recurrences with constant coefficients, signature (2,0,-1,2,-2).

Index entries for sequences related to Towers of Hanoi

FORMULA

a(n) = A341579(n-2) + A341580(n-1) + 1, for n>=2. [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^2 + x^3) /( (1-x) * (1 - x - x^2 - 2*x^4) ).

G.f.: -1/(1-x) + (1 + x + 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=3 disks

             /     \         A to D

            *       *        steps

           / \     / \      a(3) = 5

          *---B---*---*

             /     \

        D   /       \   *

       / \ /         \ / \

      *---C           *---*

     /     \         /     \

    *       *-------*       *

   / \     / \     / \     / \

  *---*---*---*   *---*---*---*

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).

PROG

(PARI) my(p=Mod('x, 'x^4-'x^3-'x^2-2)); a(n) = subst(lift(p^(n+2))\'x, 'x, 2)/2 - 1;

CROSSREFS

Cf. A341579, A341580.

Sequence in context: A102688 A236559 A275388 * A001629 A159230 A181366

Adjacent sequences:  A341578 A341579 A341580 * A341582 A341583 A341584

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 21 17:04 EDT 2021. Contains 343156 sequences. (Running on oeis4.)