

A160002


Number of moves needed to solve 4peg 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

Table of n, a(n) for n=0..20.
A Chinese web page containing the problem and the first 13 terms
KeyTo9_Fans, A picture showing the best moving pattern for n<=32
Paul K. Stockmeyer, Variations on the FourPost Tower of Hanoi Puzzle, Congressus Numerantium 102 (1994), pp. 312.
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^(na1)+3^(ba)+3^(ba+cd1)+3^(ed)+3^(nb+ac)+3^(be)3^(nb+ac1)/23^(be1)/2+(1)^(nb)*(3^(ac)1)/2+(1)^(ba)*3^(ae)/2(1)^(ba)*3^(ce)/23}, 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


STATUS

approved



