A338089 -id:A338089 - 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.

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

N. J. A. Sloane

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

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

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

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

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

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

[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

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

a(n)=([0,1,0; 0,0,1; -2,0,3]^n*[0;1;5])[1,1] \\ Charles R Greathouse IV, Jun 15 2015

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

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

A338024 Minimal number of moves for the cyclic variant of Hanoi's tower for 4 pegs and n disks, with the final peg one step away.

Original entry on oeis.org

1, 6, 15, 28, 57, 98, 179, 304, 521, 894, 1519, 2576, 4381, 7434, 12603, 21380, 36265, 61486, 104263, 176808, 299797

Offset: 1

Paul Zimmermann, Oct 07 2020

			For n=2, assume the two disks are on North initially, first move the smallest one to West in 3 moves, then the largest one to East in 1 move, and the smallest one to East also in 2 moves, with a total of 6 moves. Each disk has a number of moves which is 1 mod 4, thus a(n) = n mod 4.

Martin Ehrenstein, (C++) Program

Cf. A292764, A338089.

Conjecture: a(n) = a(n-1) + a(n-2) + a(n-3) - 2*a(n-5) for n > 11.

Conjectured g.f.: x*(1+5*x+8*x^2+6*x^3+8*x^4+8*x^6-4*x^8+4*x^9-4*x^10)/((1-x)*(1+x)*(1-x-2*x^3)). - Stefano Spezia, Oct 07 2020 after Paul Zimmermann

a(17)-a(21) from Martin Ehrenstein, Oct 25 2020

A005666 Minimal number of moves for the cyclic variant of the Towers of Hanoi for 3 pegs and n disks, with the final peg two steps away.

Original entry on oeis.org

0, 2, 7, 21, 59, 163, 447, 1223, 3343, 9135, 24959, 68191, 186303, 508991, 1390591, 3799167, 10379519, 28357375, 77473791, 211662335, 578272255, 1579869183, 4316282879, 11792304127, 32217174015, 88018956287, 240472260607, 656982433791, 1794909388799

Offset: 0

N. J. A. Sloane

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

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

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
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.
Amir Sapir, The Tower of Hanoi with Forbidden Moves, The Computer J. 47 (1) (2004) 20, case (ii), cyclic.
Index entries for sequences related to Towers of Hanoi
Index entries for linear recurrences with constant coefficients, signature (3,0,-2).

Cf. A005665, A052945 (first differences).

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

[Floor((1/(4*Sqrt(3)))*((1+Sqrt(3))^(n+2)-(1-Sqrt(3))^(n+2))-1): n in [0..30]]; // Vincenzo Librandi, Sep 03 2015

CoefficientList[Series[z (2 + z)/(z - 1)/(2 z^2 + 2 z - 1), {z, 0, 22}], z] (* Michael De Vlieger, Sep 02 2015 *)
LinearRecurrence[{3,0,-2},{0,2,7},30] (* Harvey P. Dale, Jul 28 2025 *)

a(n) = (1/(4*s3))*((1+s3)^(n+2)-(1-s3)^(n+2))-1 where s3 = sqrt(3).
a(n) = A028859(n) - 1.
G.f.: x*(2+x) / ( (x-1)*(2*x^2+2*x-1) ). - Simon Plouffe in his 1992 dissertation
From Paul Zimmermann, Feb 07 2018: (Start)
a(n) = 2*a(n-1)+2*a(n-2)+3 (same recurrence as A005665).
a(n) = 2*a(n-1)+c(n-1)+2 where c(n) = 2*a(n-1)+1 stands for A005665. (End)
E.g.f.: exp(x)*(3*cosh(sqrt(3)*x) + 2*sqrt(3)*sinh(sqrt(3)*x) - 3)/3. - Stefano Spezia, Apr 11 2025

Name clarified by Paul Zimmermann, Feb 09 2018

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

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.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

Formula

Extensions

A338024 Minimal number of moves for the cyclic variant of Hanoi's tower for 4 pegs and n disks, with the final peg one step away.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A005666 Minimal number of moves for the cyclic variant of the Towers of Hanoi for 3 pegs and n disks, with the final peg two steps away.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

Formula

Extensions