A160002 - OEIS

%I #35 Aug 06 2024 10:16:10

%S 0,3,10,19,34,57,88,123,176,253,342,449,572,749,980,1261,1560,1903,

%T 2328,2889,3562,4377,5276,6247

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

%C Move n disks from the first peg to the last peg. Disks can only move between adjacent pegs in a move.

%C 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.

%C 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

%H Baidu, <a href="http://tieba.baidu.com/f?kz=318545067">Four Pillar Tower of Hanoi Upgraded Version</a> (Chinese web page with the problem and first 13 terms).

%H P. Bastian, D. Kranzlmüller, H. Brüchle, and G. Mathias, <a href="https://doku.lrz.de/display/PUBLIC/Books+with+results+on+LRZ+HPC+Systems">High Performance Computing</a> in Science and Engineering, Garching/Munich 2022, page 255.

%H A. M. Hinz, B. Lužar, and C. Petr, <a href="https://doi.org/10.1016/j.dam.2021.05.019">The Dudeney-Stockmeyer Conjecture</a>, Discrete Appl. Math. 319 (2022) 19-26.

%H KeyTo9_Fans, <a href="http://bbs.emath.ac.cn/thread-563-6-1.html">A picture showing the best moving pattern for n<=32</a>

%H Paul K. Stockmeyer, <a href="http://www.cs.wm.edu/~pkstoc/boca.pdf">Variations on the Four-Post Tower of Hanoi Puzzle</a>, Congressus Numerantium 102 (1994), pp. 3-12.

%H Paul K. Stockmeyer and Fred Lunnon, <a href="https://citeseerx.ist.psu.edu/pdf/eda4deedb291703eb5d6d6d3fac496b757ba8732">New Variations on the Tower of Hanoi</a>.

%H <a href="/index/To#Hanoi">Index entries for sequences related to Towers of Hanoi</a>

%F 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

%e For n=2, 10 moves needed:

%e 0: {1,2},{},{},{}

%e 1: {2},{1},{},{}

%e 2: {2},{},{1},{}

%e 3: {2},{},{},{1}

%e 4: {},{2},{},{1}

%e 5: {},{},{2},{1}

%e 6: {},{},{1,2},{}

%e 7: {},{1},{2},{}

%e 8: {},{1},{},{2}

%e 9: {},{},{1},{2}

%e 10: {},{},{},{1,2}

%Y Cf. A007664.

%K nonn

%O 0,2

%A _Yi Yang_, Apr 29 2009

%E Values up to n=19 checked and Yang's bound proved to equal a(20) by _Paul Zimmermann_, Feb 21 2018

%E Values for n=21,22,23 added by _Ciril Petr_, May 03 2023