A005665 Tower of Hanoi with 3 pegs and cyclic moves only (clockwise). (Formerly M3857)

0, 1, 5, 15, 43, 119, 327, 895, 2447, 6687, 18271, 49919, 136383, 372607, 1017983, 2781183, 7598335, 20759039, 56714751, 154947583, 423324671, 1156544511, 3159738367, 8632565759, 23584608255, 64434348031, 176037912575, 480944521215, 1313964867583, 3589818777599, 9807567290367

Offset

0,3

Comments

This looks like sequence A(0,1;2,2;3) of the family of sequences [a,b:c,d:k] considered by Gary Detlefs, and treated as A(a,b;c,d;k) in the W. Lang link given below. - Wolfdieter Lang, Oct 18 2010

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

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

S. Alejandre, Legend of Towers of Hanoi

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

A. M. Hinz, S. Klavžar, U. Milutinović, C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 249. Book's website

Wolfdieter Lang, Notes on certain inhomogeneous three term recurrences.

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.

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

Index entries for sequences related to Towers of Hanoi

Formula

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

From Paul Barry, Sep 05 2006: (Start)

a(n) = ((sqrt(3)+1)^(n+1) + (sqrt(3)-1)^(n+1)*(-1)^n)*sqrt(3)/6 - 1. (End)

a(n) = 2*a(n-1) + 2*a(n-2) + 3. - John W. Layman

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

a(n) = 3*a(n-1) - 2*a(n-3), a(0)=0, a(1)=1, a(2)=5 (from the given o.g.f.). Observed by Gary Detlefs. See the W. Lang link. - Wolfdieter Lang, Oct 18 2010

a(n) = 2*A005666(n-1) + 1. - Michel Marcus, Nov 02 2012

a(n) = Sum_{k=1..n} A026150(k). - Ivan N. Ianakiev, Nov 22 2019

E.g.f.: (1/3)*exp(x)*(-3 + 3*cosh(sqrt(3)*x) + sqrt(3)*sinh(sqrt(3)*x)). - Stefano Spezia, Nov 22 2019

Mathematica

a[n_] := Simplify[ ((1 + Sqrt[3])^(n+1) - (1 - Sqrt[3])^(n+1))*Sqrt[3]/6 - 1]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Dec 14 2011, after Paul Barry *)
LinearRecurrence[{3, 0, -2}, {0, 1, 5}, 40] (* Harvey P. Dale, Mar 30 2015 *)

Prog

(Magma) [Floor(((Sqrt(3)+1)^(n+1)+(Sqrt(3)-1)^(n+1)*(-1)^n)*Sqrt(3)/6-1): n in [0..30] ]; // Vincenzo Librandi, Aug 19 2011
(Haskell)
a005665 n = a005665_list !! (n-1)
a005665_list = 0 : 1 : 5 : zipWith (-)
               (map (* 3) $ drop 2 a005665_list) (map (* 2) a005665_list)
-- Reinhard Zumkeller, May 01 2013
(PARI) a(n)=([0, 1, 0; 0, 0, 1; -2, 0, 3]^n*[0; 1; 5])[1, 1] \\ Charles R Greathouse IV, Jun 15 2015

Crossrefs

Cf. A005666, A007664, A007665, A026150 (first differences).

Sequence in context: A200760 A032193 A178965 * A025471 A064453 A059251

Adjacent sequences: A005662 A005663 A005664 * A005666 A005667 A005668

Keyword

nonn,nice,easy

Author

N. J. A. Sloane

Extensions

More terms from Vincenzo Librandi, Aug 19 2011

Name clarified by Paul Zimmermann, Feb 21 2018

Status

approved