

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, 4377, 5276, 6251, 7392, 8779, 10488, 12469, 14832, 17497, 20228, 23377, 27082
(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.


LINKS

Table of n, a(n) for n=0..32.
A Chinese web page containing the problem and the first 13 terms
KeyTo9_Fans, A picture shown the best moving pattern for n<=32 [From Yi Yang, Apr 11 2010]


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. [From 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. [From R. J. Mathar, Apr 30 2009]
Sequence in context: A010896 A234940 A135446 * A027177 A048343 A056789
Adjacent sequences: A159999 A160000 A160001 * A160003 A160004 A160005


KEYWORD

nonn


AUTHOR

Yi Yang, Apr 29 2009


EXTENSIONS

Added three more terms.  Yi Yang, Nov 02 2009


STATUS

approved



