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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005665 Tower of Hanoi with cyclic moves only.
(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

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. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 18.

Math. Mag., vol. 67, no. 5, p. 339, Dec '94.

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

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

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

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.

Wolfdieter Lang, Notes on certain inhomogeneous three term recurrences.

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

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

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

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.

Content is available under The OEIS End-User License Agreement .

Last modified September 3 03:40 EDT 2014. Contains 246369 sequences.