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,2

Comments

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

Links

Table of n, a(n) for n=1..42.

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

Formula

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)

Maple

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

Mathematica

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

Prog

(PARI) a(n) = (3+(n % 2))*(2^(n\2)) - 4; \\ Michel Marcus, Sep 14 2021
(Python)
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

Crossrefs

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

Sequence in context: A014557 A023598 A263615 * A303748 A173725 A300414

Adjacent sequences: A347786 A347787 A347788 * A347790 A347791 A347792

Keyword

nonn,easy

Author

John Bonomo, Sep 13 2021

Status

approved