A005665 Minimal number of moves for the cyclic variant of the Towers of Hanoi for 3 pegs and n disks, with the final peg one step away.

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

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

Comments

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

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

Crossrefs

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

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

Programs

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

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

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

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

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

Extensions

More terms from Vincenzo Librandi, Aug 19 2011

Name clarified by Paul Zimmermann, Feb 21 2018

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