A160002 Number of moves needed to solve 4-peg Tower of Hanoi Puzzle with n disks.

0, 3, 10, 19, 34, 57, 88, 123, 176, 253, 342, 449, 572, 749, 980, 1261, 1560, 1903, 2328, 2889, 3562, 4377, 5276, 6247

Offset: 0

Author

Yi Yang, Apr 29 2009

Keywords

• nonn

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.

Values for n=21, 22, 23 were computed on SuperMUC-NG by Andreas M. Hinz and Ciril Petr during 2020-2021. The value for n = 23 is the first one that is less than Yang's bound, so the optimal strategy is still an open problem. - Ciril Petr, May 03 2023

Examples

			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}
		

Links

• Baidu, Four Pillar Tower of Hanoi Upgraded Version (Chinese web page with the problem and first 13 terms).
• P. Bastian, D. Kranzlmüller, H. Brüchle, and G. Mathias, High Performance Computing in Science and Engineering, Garching/Munich 2022, page 255.
• A. M. Hinz, B. Lužar, and C. Petr, The Dudeney-Stockmeyer Conjecture, Discrete Appl. Math. 319 (2022) 19-26.
• 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 and Fred Lunnon, New Variations on the Tower of Hanoi.
• Index entries for sequences related to Towers of Hanoi

Crossrefs

Cf. A007664.

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

Extensions

Values up to n=19 checked and Yang's bound proved to equal a(20) by Paul Zimmermann, Feb 21 2018

Values for n=21,22,23 added by Ciril Petr, May 03 2023