cp's OEIS Frontend

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.

%I A005665 M3857 #100 Nov 01 2024 20:33:12
%S A005665 0,1,5,15,43,119,327,895,2447,6687,18271,49919,136383,372607,1017983,
%T A005665 2781183,7598335,20759039,56714751,154947583,423324671,1156544511,
%U A005665 3159738367,8632565759,23584608255,64434348031,176037912575,480944521215,1313964867583,3589818777599,9807567290367
%N 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.
%C A005665 Original name was: Tower of Hanoi with 3 pegs and cyclic moves only (clockwise). - _Jianing Song_, Nov 01 2024
%C A005665 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
%D A005665 R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 18.
%D A005665 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005665 Vincenzo Librandi, <a href="/A005665/b005665.txt">Table of n, a(n) for n = 0..1000</a>
%H A005665 S. Alejandre, <a href="https://web.archive.org/web/20040314132214/http://www.rialto.k12.ca.us:80/frisbie/mathfair/hanoilegend.html">Legend of Towers of Hanoi</a>
%H A005665 J.-P. Allouche, <a href="http://dx.doi.org/10.1016/0304-3975(94)90064-7">Note on the cyclic towers of Hanoi</a>, Theoret. Comput. Sci., 123 (1994), 3-7.
%H A005665 M. D. Atkinson, <a href="http://www.cs.otago.ac.nz/staffpriv/mike/Papers/Hanoi/CyclicHanoi.pdf">The Cyclic Towers of Hanoi</a>, Info. Proc. Letters, 13 (1981), 118-119.
%H A005665 R. K. Guy, <a href="/A005665/a005665_1.pdf">Letter to N. J. A. Sloane, 1976</a>
%H A005665 A. M. Hinz, S. Klavžar, U. Milutinović, C. Petr, <a href="http://dx.doi.org/10.1007/978-3-0348-0237-6">The Tower of Hanoi - Myths and Maths</a>, Birkhäuser 2013. See page 249. <a href="http://tohbook.info">Book's website</a>
%H A005665 Wolfdieter Lang, <a href="/A005665/a005665.pdf">Notes on certain inhomogeneous three term recurrences.</a>
%H A005665 Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H A005665 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H A005665 D. G. Poole, <a href="http://www.jstor.org/stable/2690991">The towers and triangles of Professor Claus (or, Pascal knows Hanoi)</a>, Math. Mag., 67 (1994), 323-344.
%H A005665 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,0,-2).
%H A005665 <a href="/index/To#Hanoi">Index entries for sequences related to Towers of Hanoi</a>
%F A005665 G.f.: x*(1+2*x)/((1-x)*(1-2*x-2*x^2)). - _Simon Plouffe_ in his 1992 dissertation
%F A005665 From _Paul Barry_, Sep 05 2006: (Start)
%F A005665 a(n) = ((sqrt(3)+1)^(n+1) + (sqrt(3)-1)^(n+1)*(-1)^n)*sqrt(3)/6 - 1. (End)
%F A005665 a(n) = 2*a(n-1) + 2*a(n-2) + 3. - _John W. Layman_
%F A005665 a(n) = (1/(2*s3))*((1+s3)^(n+1) - (1-s3)^(n+1)) - 1 where s3 = sqrt(3).
%F A005665 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
%F A005665 a(n) = 2*A005666(n-1) + 1. - _Michel Marcus_, Nov 02 2012
%F A005665 a(n) = Sum_{k=1..n} A026150(k). - _Ivan N. Ianakiev_, Nov 22 2019
%F A005665 E.g.f.: (1/3)*exp(x)*(-3 + 3*cosh(sqrt(3)*x) + sqrt(3)*sinh(sqrt(3)*x)). - _Stefano Spezia_, Nov 22 2019
%t A005665 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_ *)
%t A005665 LinearRecurrence[{3,0,-2},{0,1,5},40] (* _Harvey P. Dale_, Mar 30 2015 *)
%o A005665 (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
%o A005665 (Haskell)
%o A005665 a005665 n = a005665_list !! (n-1)
%o A005665 a005665_list = 0 : 1 : 5 : zipWith (-)
%o A005665                (map (* 3) $ drop 2 a005665_list) (map (* 2) a005665_list)
%o A005665 -- _Reinhard Zumkeller_, May 01 2013
%o A005665 (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
%Y A005665 Cf. A005666, A007664, A007665, A026150 (first differences).
%Y A005665 Cf. A338024, A292764, A338089 (4 pegs).
%K A005665 nonn,nice,easy
%O A005665 0,3
%A A005665 _N. J. A. Sloane_
%E A005665 More terms from _Vincenzo Librandi_, Aug 19 2011
%E A005665 Name clarified by _Paul Zimmermann_, Feb 21 2018
%E A005665 New name based on the name of A338024, A292764, and A338089 by _Jianing Song_, Nov 01 2024