login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005665 Tower of Hanoi with cyclic moves only (clockwise).
(Formerly M3857)
3
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 (list; graph; refs; listen; history; text; internal format)
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 G. Detlefs, and treated as A(a,b;c,d;k) in the W. Lang link given below. [Wolfdieter Lang, Oct 18 2010]

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

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.

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.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 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).

FORMULA

G.f.: x*(1+2*x)/(1-3*x+2*x^3); a(n)=((sqrt(3)+1)^(n+1)+(sqrt(3)-1)^(n+1)*(-1)^n)*sqrt(3)/6-1. - Paul Barry, Sep 05 2006

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 G. Detlefs. See the W. Lang link. - Wolfdieter Lang, Oct 18 2010

MAPLE

A005665:=z*(1+2*z)/(z-1)/(2*z**2+2*z-1); [Conjectured (correctly) by Simon Plouffe in his 1992 dissertation.]

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.

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified July 1 01:17 EDT 2016. Contains 274319 sequences.