A341579 -id:A341579 - cp's OEIS frontend

A347789 a(n) is the number of times that only 2 pegs have disks on them during the optimal solution to a Towers of Hanoi problem with n disks.

0, 2, 4, 8, 12, 20, 28, 44, 60, 92, 124, 188, 252, 380, 508, 764, 1020, 1532, 2044, 3068, 4092, 6140, 8188, 12284, 16380, 24572, 32764, 49148, 65532, 98300, 131068, 196604, 262140, 393212, 524284, 786428, 1048572, 1572860, 2097148, 3145724, 4194300, 6291452

Offset: 1

John Bonomo, Sep 13 2021

Zero together with the partial sum of the even terms of A016116. - Omar E. Pol, Sep 14 2021

For n >= 2, a(n+1) is the number of n X n arrays of 0's and 1's with every 2 X 2 square having density exactly 1. - David desJardins, Oct 27 2022

J. Bonomo, Back to the Tower, The College Mathematics Journal 52(2021), 265-273.
Index entries for sequences related to Towers of Hanoi
Index entries for linear recurrences with constant coefficients, signature (1,2,-2).

Cf. A016116, A027383, A052955, A341579.

The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A029744 = {s(n), n>=1}, the numbers 2^k and 3*2^k, as the parent: A029744 (s(n)); A052955 (s(n)-1), A027383 (s(n)-2), A354788 (s(n)-3), A347789 (s(n)-4), A209721 (s(n)+1), A209722 (s(n)+2), A343177 (s(n)+3), A209723 (s(n)+4); A060482, A136252 (minor differences from A354788 at the start); A354785 (3*s(n)), A354789 (3*s(n)-7). The first differences of A029744 are 1,1,1,2,2,4,4,8,8,... which essentially matches eight sequences: A016116, A060546, A117575, A131572, A152166, A158780, A163403, A320770. The bisections of A029744 are A000079 and A007283. - N. J. A. Sloane, Jul 14 2022

a:= proc(n) option remember;
      `if`(n<3, 2*n-2, 2*(a(n-2)+2))
    end:
seq(a(n), n=1..42);  # Alois P. Heinz, Sep 14 2021

LinearRecurrence[{1, 2, -2}, {0, 2, 4}, 42] (* Jean-François Alcover, May 14 2022 *)

a(n) = (3+(n % 2))*(2^(n\2)) - 4; \\ Michel Marcus, Sep 14 2021

def a(n): return (3 + n%2) * 2**(n//2) - 4
print([a(n) for n in range(1, 43)]) # Michael S. Branicky, Sep 14 2021

a(n) = (3+(n mod 2))*(2^floor(n/2)) - 4.
a(n) = 4 * A052955(n-3) for n >= 3. - Joerg Arndt, Sep 14 2021
a(n) = A027383(n) - 2. - Omar E. Pol, Sep 14 2021
a(n) = 2 * A027383(n-2) for n >= 2. - Alois P. Heinz, Sep 14 2021
From Stefano Spezia, Sep 14 2021: (Start)
G.f.: 2*x^2*(1+x)/((1-x)*(1-2*x^2)).
a(n) = a(n-1) + 2*a(n-2) - 2*a(n-3) for n > 3. (End)

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.

Original entry on oeis.org

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

Offset: 0

Kevin Ryde, Feb 16 2021

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.

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.

			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.

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).
Index entries for sequences related to Towers of Hanoi

Cf. A341579, A341581.

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

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

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

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.

Original entry on oeis.org

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

Offset: 0

Kevin Ryde, Feb 16 2021

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.

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.

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

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

Cf. A341579, A341580.

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

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

A341582 Number of simple moves of the smallest disk in the solution to the Towers of Hanoi exchanging disks puzzle with 3 pegs and n disks.

Original entry on oeis.org

0, 1, 2, 4, 6, 12, 22, 42, 76, 142, 262, 488, 902, 1674, 3100, 5750, 10654, 19752, 36606, 67858, 125772, 233134, 432118, 800968, 1484630, 2751866, 5100732, 9454534, 17524526, 32482792, 60208782, 111600642, 206858476, 383424702, 710700742, 1317326728, 2441744422

Offset: 0

Kevin Ryde, Feb 16 2021

Stockmeyer et al. show the shortest solution to the puzzle is f(n) = A341579(n) steps. They offer as an exercise for the reader to prove that the number of exchanges made within the solution is f(n-1) and the remaining a(n) = f(n) - f(n-1) here is the number of simple moves of the smallest disk (move-only, not exchange).

			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
              B---*             solution
             /     \            A to H,
            C       *           within
           / \     / \          which
          *---D---*---*         a(3) = 4
             /     \            smallest
        *   /       \   *       disk moves:
       / \ /         \ / \       AB, CD,
      F---E           *---*      EF, GH
     /     \         /     \
    G       I-------*       *
   / \     / \     / \     / \
  H---*---*---J   *---*---*---*
For n=4, the first half of the solution is A to J per A341580.  The smallest disk moves are AB, CD, IJ, and twice those is a(4) = 2*3 = 6 since J across to the next subgraph is an exchange, not a smallest disk move.

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. See section 5 exercise 2.
Index entries for linear recurrences with constant coefficients, signature (1,1,0,2).
Index entries for sequences related to Towers of Hanoi

Cf. A341579, A341580.

A341582list[nmax_]:=LinearRecurrence[{1,1,0,2},{0,1,2,4},nmax+1];A341582list[50] (* Paolo Xausa, Jun 29 2023 *)

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

a(n) = A341579(n) - A341579(n-1), for n>=1. [Stockmeyer et al.]
a(n) = a(n-1) + a(n-2) + 2*a(n-4).
G.f.: x*(1 + x + x^2)/(1 - x - x^2 - 2*x^4)

A341583 Geometric length of the solution to the Towers of Hanoi exchanging disks puzzle with 3 pegs and n disks.

Original entry on oeis.org

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

Offset: 0

Kevin Ryde, Feb 16 2021

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

			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.

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

Cf. A341579.

A341583list[nmax_]:=LinearRecurrence[{3,-1,-2,2,-4},{0,1,3,8,18},nmax+1];A341583list[50] (* Paolo Xausa, Jun 29 2023 *)

my(p=Mod('x,'x^4-'x^3-'x^2-2), f=7*'x^3+5*'x^2+3*'x+6); a(n) = (7<

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

cp's OEIS Frontend

A347789 a(n) is the number of times that only 2 pegs have disks on them during the optimal solution to a Towers of Hanoi problem with n disks.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A341582 Number of simple moves of the smallest disk in the solution to the Towers of Hanoi exchanging disks puzzle with 3 pegs and n disks.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A341583 Geometric length of the solution to the Towers of Hanoi exchanging disks puzzle with 3 pegs and n disks.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula