A005666 Tower of Hanoi with 3 pegs and cyclic moves only (counterclockwise). (Formerly M1755)

0, 2, 7, 21, 59, 163, 447, 1223, 3343, 9135, 24959, 68191, 186303, 508991, 1390591, 3799167, 10379519, 28357375, 77473791, 211662335, 578272255, 1579869183, 4316282879, 11792304127, 32217174015, 88018956287, 240472260607, 656982433791, 1794909388799

Offset

0,2

References

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 18.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Table of n, a(n) for n=0..28.

J.-P. Allouche, Note on the cyclic towers of Hanoi, Theoret. Comput. Sci., 123 (1994), 3-7.

M. D. Atkinson, The Cyclic Towers of Hanoi, Info. Proc. Letters, 13 (1981), 118-119.

R. K. Guy, Letter to N. J. A. Sloane, 1976

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992

D. G. Poole, The towers and triangles of Professor Claus (or, Pascal knows Hanoi), Math. Mag., 67 (1994), 323-344.

Amir Sapir, The Tower of Hanoi with Forbidden Moves, The Computer J. 47 (1) (2004) 20, case (ii), cyclic.

Index entries for sequences related to Towers of Hanoi

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

Formula

a(n) = (1/(4*s3))*((1+s3)^(n+2)-(1-s3)^(n+2))-1 where s3 = sqrt(3).

a(n) = A028859(n) - 1.

G.f.: x*(2+x) / ( (x-1)*(2*x^2+2*x-1) ). - Simon Plouffe in his 1992 dissertation

From Paul Zimmermann, Feb 07 2018: (Start)

a(n) = 2*a(n-1)+2*a(n-2)+3 (same recurrence as A005665).

a(n) = 2*a(n-1)+c(n-1)+2 where c(n) = 2*a(n-1)+1 stands for A005665.

(End)

Mathematica

CoefficientList[Series[z (2 + z)/(z - 1)/(2 z^2 + 2 z - 1), {z, 0, 22}], z] (* Michael De Vlieger, Sep 02 2015 *)

Prog

(Magma) [Floor((1/(4*Sqrt(3)))*((1+Sqrt(3))^(n+2)-(1-Sqrt(3))^(n+2))-1): n in [0..30]]; // Vincenzo Librandi, Sep 03 2015

Crossrefs

Cf. A005665, A052945 (first differences).

Sequence in context: A018036 A007050 A320811 * A353094 A291411 A159972

Adjacent sequences: A005663 A005664 A005665 * A005667 A005668 A005669

Keyword

nonn,easy

Author

N. J. A. Sloane

Extensions

Name clarified by Paul Zimmermann, Feb 09 2018

Status

approved