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

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

Links

Table of n, a(n) for n=0..23.

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

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<=a<b<n. When n>32, 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

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

Status

approved