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!)
A341583 Geometric length of the solution to the Towers of Hanoi exchanging disks puzzle with 3 pegs and n disks. 2
0, 1, 3, 8, 18, 42, 94, 208, 450, 966, 2052, 4330, 9074, 18920, 39266, 81182, 167268, 343634, 704122, 1439496, 2936906, 5981174, 12161332, 24691514, 50066690, 101400616, 205150098, 414653998, 837377988, 1689714242, 3407154474, 6865700808, 13826659450, 27829885126 (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 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.

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.

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) = d(n) in section 5 exercise 5.

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

Index entries for sequences related to Towers of Hanoi

FORMULA

a(n) = (7*2^n - A341579(n+3) + A341579(n))/2.

a(n) = 3*a(n-1) - a(n-2) - 2*a(n-3) + 2*a(n-4) - 4*a(n-5).

G.f.: x * (1 - x) * (1 + x + x^2) / ( (1 - 2*x) * (1 - x - x^2 - 2*x^4) ).

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

EXAMPLE

The graph embedding in a triangular grid is (as drawn by Scorer et al.),

                A

               / \              n=3 disks

              *---*              A to D

             /     \            geometric

            *       *         length along

           / \     / \          the path

          *---B---*---*         a(3) = 8

             /     \

        *   .       \   *

       / \ /         \ / \

      *---C           *---*

     /     \         /     \

    *       *-------*       *

   / \     / \     / \     / \

  D---*---*---*   *---*---*---*

B to C is where disks s=1 and s+1=2 exchange which is geometric length 2^s = 2.

PROG

(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;

CROSSREFS

Cf. A341579.

Sequence in context: A026679 A191524 A026756 * A216631 A026384 A322496

Adjacent sequences:  A341580 A341581 A341582 * A341584 A341585 A341586

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 May 12 07:28 EDT 2021. Contains 343821 sequences. (Running on oeis4.)