This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A160002 Number of moves needed to solve 4-peg Tower of Hanoi Puzzle with n disks. 0
 0, 3, 10, 19, 34, 57, 88, 123, 176, 253, 342, 449, 572, 749, 980, 1261, 1560, 1903, 2328, 2889, 3562 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,2 COMMENTS Move n disks from the first peg to the last peg. Disks can only move between adjacent pegs in a move. Upper bounds by Yi Yang using 'best moving pattern' for n = 21..32 are: 4377, 5276, 6251, 7392, 8779, 10488, 12469, 14832, 17497, 20228, 23377, 27082. LINKS KeyTo9_Fans, A picture showing the best moving pattern for n<=32 Paul K. Stockmeyer, Variations on the Four-Post Tower of Hanoi Puzzle, Congressus Numerantium 102 (1994), pp. 3-12. Paul K. Stockmeyer, Fred Lunnon, New Variations on the Tower of Hanoi. FORMULA Given the terms of n<=6, we can calculate f(n) for 7<=n<=32 using this formula: f(n)=min{f(a)+f(c)+2f(d)+f(e)+3^(n-a-1)+3^(b-a)+3^(b-a+c-d-1)+3^(e-d)+3^(n-b+a-c)+3^(b-e)-3^(n-b+a-c-1)/2-3^(b-e-1)/2+(-1)^(n-b)*(3^(a-c)-1)/2+(-1)^(b-a)*3^(a-e)/2-(-1)^(b-a)*3^(c-e)/2-3}, which 0<=d<=e<=c<=a32, it is hard to determine whether this formula still hold. Maybe a new moving pattern will appear for larger n. [Yi Yang, Apr 11 2010] EXAMPLE For n=2, 10 moves needed: 0: {1,2},{},{},{} 1: {2},{1},{},{} 2: {2},{},{1},{} 3: {2},{},{},{1} 4: {},{2},{},{1} 5: {},{},{2},{1} 6: {},{},{1,2},{} 7: {},{1},{2},{} 8: {},{1},{},{2} 9: {},{},{1},{2} 10: {},{},{},{1,2} CROSSREFS Cf. A007664. Sequence in context: A010896 A234940 A135446 * A294421 A027177 A048343 Adjacent sequences:  A159999 A160000 A160001 * A160003 A160004 A160005 KEYWORD nonn AUTHOR Yi Yang, Apr 29 2009 EXTENSIONS Values up to n=19 checked and Yang's bound proved to equal a(20) by Paul Zimmermann, Feb 21 2018 STATUS approved

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

Last modified October 13 18:14 EDT 2019. Contains 327981 sequences. (Running on oeis4.)