A007664 -id:A007664 - cp's OEIS frontend

A143807 Number of geodesics between a pair of perfect states in the Tower of Hanoi with 4 pegs and n disks.

1, 2, 2, 22, 40, 18, 2468, 11698, 11426, 2178, 74056628

Offset: 1

Jason Behrstock (jason(AT)math.columbia.edu), Sep 01 2008

Sequence A007664 gives the lengths of the geodesics being counted by the present sequence (conjecturally this is true for all n; experimentally it is true for the first 20 terms)

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

Original entry on oeis.org

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

Yi Yang, Apr 29 2009

nonn

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

			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}

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

Cf. A007664.

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

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

A382111 Maximum number of moves required to transition from the initial configuration (all disks on the first peg) to any possible configuration in the Towers of Hanoi puzzle with 4 pegs and n disks.

Original entry on oeis.org

0, 1, 3, 5, 9, 13, 17, 25, 33, 41, 49, 65, 81, 97, 113, 130, 161, 193, 225, 257, 294

Offset: 0

Geethan Pfeifer, Mar 16 2025

Values for n = 1..20 taken from Korf, 2004 (see table 2).
Somewhat surprisingly, this is not the same as A007664 from which first differs at a(15).
This gives a lower bound on the diameter of Hanoi graphs with k = 4.

Richard E. Korf, Best-first frontier search with delayed duplicate detection, In Proceedings of the 19th national conference on Artifical intelligence (AAAI'04). AAAI Press, (2004), 650-657.

Cf. A007664.

cp's OEIS Frontend

A143807 Number of geodesics between a pair of perfect states in the Tower of Hanoi with 4 pegs and n disks.

Views

Author

Keywords

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A382111 Maximum number of moves required to transition from the initial configuration (all disks on the first peg) to any possible configuration in the Towers of Hanoi puzzle with 4 pegs and n disks.

Views

Author

Keywords

Comments

Links

Crossrefs