login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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; 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^(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, 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 24 16:32 EDT 2017. Contains 288707 sequences.