|
| |
|
|
A160002
|
|
Number of moves needed to solve 4-peg 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; 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
| 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 (YangYi0526(AT)163.com), 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^(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. [From Yi Yang (YangYi0526(AT)163.com), 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 (mathar(AT)strw.leidenuniv.nl), Apr 30 2009]
Sequence in context: A028878 A010896 A135446 * A027177 A048343 A056789
Adjacent sequences: A159999 A160000 A160001 * A160003 A160004 A160005
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Yi Yang (YangYi0526(AT)163.com), Apr 29 2009
|
|
|
EXTENSIONS
| Added three more terms. - Yi Yang (YangYi0526(AT)163.com), Nov 02 2009
|
| |
|
|
