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

%I #55 Oct 29 2022 09:25:04

%S 0,2,4,8,12,20,28,44,60,92,124,188,252,380,508,764,1020,1532,2044,

%T 3068,4092,6140,8188,12284,16380,24572,32764,49148,65532,98300,131068,

%U 196604,262140,393212,524284,786428,1048572,1572860,2097148,3145724,4194300,6291452

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

%C Zero together with the partial sum of the even terms of A016116. - _Omar E. Pol_, Sep 14 2021

%C 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

%H J. Bonomo, <a href="https://www.tandfonline.com/doi/pdf/10.1080/07468342.2021.1941540">Back to the Tower</a>, The College Mathematics Journal 52(2021), 265-273.

%H <a href="/index/To#Hanoi">Index entries for sequences related to Towers of Hanoi</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,2,-2).

%F a(n) = (3+(n mod 2))*(2^floor(n/2)) - 4.

%F a(n) = 4 * A052955(n-3) for n >= 3. - _Joerg Arndt_, Sep 14 2021

%F a(n) = A027383(n) - 2. - _Omar E. Pol_, Sep 14 2021

%F a(n) = 2 * A027383(n-2) for n >= 2. - _Alois P. Heinz_, Sep 14 2021

%F From _Stefano Spezia_, Sep 14 2021: (Start)

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

%F a(n) = a(n-1) + 2*a(n-2) - 2*a(n-3) for n > 3. (End)

%p a:= proc(n) option remember;

%p `if`(n<3, 2*n-2, 2*(a(n-2)+2))

%p end:

%p seq(a(n), n=1..42); # _Alois P. Heinz_, Sep 14 2021

%t LinearRecurrence[{1, 2, -2}, {0, 2, 4}, 42] (* _Jean-François Alcover_, May 14 2022 *)

%o (PARI) a(n) = (3+(n % 2))*(2^(n\2)) - 4; \\ _Michel Marcus_, Sep 14 2021

%o (Python)

%o def a(n): return (3 + n%2) * 2**(n//2) - 4

%o print([a(n) for n in range(1, 43)]) # _Michael S. Branicky_, Sep 14 2021

%Y Cf. A016116, A027383, A052955, A341579.

%Y 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

%K nonn,easy

%O 1,2

%A _John Bonomo_, Sep 13 2021