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!)
A341579 Number of steps needed to solve the Towers of Hanoi exchanging disks puzzle with 3 pegs and n disks. 5
0, 1, 3, 7, 13, 25, 47, 89, 165, 307, 569, 1057, 1959, 3633, 6733, 12483, 23137, 42889, 79495, 147353, 273125, 506259, 938377, 1739345, 3223975, 5975841, 11076573, 20531107, 38055633, 70538425, 130747207, 242347849, 449206325, 832631027, 1543331769, 2860658497 (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 aim is to move a stack of n disks from one peg to another.

Stockmeyer et al. show that the number of steps in the solution is a(n), and that the sequence of steps is unique.  They offer as exercises for the reader to prove that the number of exchanges with the solution is a(n-1), and that a(n) is the largest number of steps between any two configurations (in other words a(n) is the diameter of the state graph).

LINKS

Kevin Ryde, Table of n, a(n) for n = 0..700

House of Graphs, graphs 44105, 44107, 44109.  Diameters = a(3..5).

R. S. Scorer, P. M. Grundy, and C. A. B. Smith, Some Binary Games, The Mathematical Gazette, July 1944, volume 28, number 280, pages 96-103, section 4(iii) Plane Network Game.

Paul K. Stockmeyer, C. Douglass Bateman, James W. Clark, Cyrus R. Eyster, Matthew T. Harrison, Nicholas A. Loehr, Patrick J. Rodriguez, and Joseph R. Simmons III, 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) = f(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) = 2*A341580(n-1) + 1 for n>=1. [Stockmeyer et al.]

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

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

             /     \          A to D

            *       *      a(3) = 7 steps

           / \     / \

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

             /     \

        *   /       \   *

       / \ /         \ / \

      *---C           *---*

     /     \         /     \

    *       *-------*       *

   / \     / \     / \     / \

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

The formula using A341580 is A to B distance A341580(2) = 3, the same (by symmetry) from D to C, and +1 from B to C.  B to C is where the largest disk moves to the target peg (by exchange with the second-largest).

PROG

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

CROSSREFS

Cf. A341580 (halfway), A341582 (first differences), A341583 (geometric length).

Sequence in context: A304648 A243737 A269832 * A336726 A201081 A017994

Adjacent sequences:  A341576 A341577 A341578 * A341580 A341581 A341582

KEYWORD

nonn,easy

AUTHOR

Kevin Ryde, Feb 15 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 June 24 16:28 EDT 2021. Contains 345417 sequences. (Running on oeis4.)