A005666 Minimal number of moves for the cyclic variant of the Towers of Hanoi for 3 pegs and n disks, with the final peg two steps away.

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

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

Comments

Original name was: Tower of Hanoi with 3 pegs and cyclic moves only (counterclockwise). - Jianing Song, Nov 01 2024

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

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

Crossrefs

Cf. A005665, A052945 (first differences).

Cf. A338024, A292764, A338089 (4 pegs).

Programs

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

Mathematica

CoefficientList[Series[z (2 + z)/(z - 1)/(2 z^2 + 2 z - 1), {z, 0, 22}], z] (* Michael De Vlieger, Sep 02 2015 *)
LinearRecurrence[{3,0,-2},{0,2,7},30] (* Harvey P. Dale, Jul 28 2025 *)

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)

E.g.f.: exp(x)*(3*cosh(sqrt(3)*x) + 2*sqrt(3)*sinh(sqrt(3)*x) - 3)/3. - Stefano Spezia, Apr 11 2025

Extensions

Name clarified by Paul Zimmermann, Feb 09 2018

New name based on the name of A338024, A292764, and A338089 by Jianing Song, Nov 01 2024