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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A183111 Magnetic Tower of Hanoi, number of moves of disk number k, optimally solving the [RED ; BLUE ; NEUTRAL] or [NEUTRAL ; RED ; BLUE] pre-colored puzzle. 20
0, 1, 3, 9, 25, 75, 223, 665, 1993, 5971, 17903, 53697, 161065, 483163, 1449439, 4348233, 13044585, 39133571, 117400431, 352200881, 1056601993 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

A. The Magnetic Tower of Hanoi puzzle is described in link 1 listed below. The Magnetic Tower is pre-colored. Pre-coloring is [RED ; BLUE ; NEUTRAL] or [NEUTRAL ; RED ; BLUE], given in [Source ; Intermediate ; Destination] order. The solution algorithm producing the sequence is optimal (the sequence presented gives the minimum number of moves to solve the puzzle for the given pre-coloring configurations). Optimal solutions are discussed and their optimality is proved in link 2 listed below.

B. Disk numbering is from largest disk (k = 1) to smallest disk (k = N)

C. The above-listed "original" sequence generates a "partial-sums" sequence - describing the total number of moves required to solve the puzzle.

D. The number of moves of disk k, for large k, is close to (10/11)*3^(k-1) ~ 0.909*3^(k-1). Series designation: P909(k).

LINKS

Table of n, a(n) for n=0..20.

Uri Levy, The Magnetic Tower of Hanoi, Journal of Recreational Mathematics, Volume 35 Number 3 (2006),  2010, pp 173. arXiv:1003.0225

U. Levy, Magnetic Towers of Hanoi and their Optimal Solutions, arxiv:1011.3834

Web applet to play The Magnetic Tower of Hanoi

Index entries for linear recurrences with constant coefficients, signature (3,1,-1,-6).

FORMULA

G.f. -x*(-1+4*x^3+x^2) / ( (3*x-1)*(2*x^3+x^2-1) ).

Recurrence Relations (a(n)=P909(n) as in referenced paper):

a(n) = a(n-2) + a(n-3) + 2*3^(n-2) + 2*3^(n-4) ; n >= 4

Closed-Form Expression:

Define:

λ1 = [1+sqrt(26/27)]^(1/3) +  [1-sqrt(26/27)]^(1/3)

λ2 = -0.5* λ1 + 0.5*i*{[sqrt(27)+sqrt(26)]^(1/3)- [sqrt(27)-sqrt(26)]^(1/3)}

λ3 = -0.5* λ1 - 0.5*i*{[sqrt(27)+sqrt(26)]^(1/3)- [sqrt(27)-sqrt(26)]^(1/3)}

AP = [(1/11)* λ2* λ3 - (3/11)*(λ2 + λ3) + (9/11)]/[( λ2 - λ1)*( λ3 - λ1)]

BP = [(1/11)* λ1* λ3 - (3/11)*(λ1 + λ3) + (9/11)]/[( λ1 - λ2)*( λ3 - λ2)]

CP = [(1/11)* λ1* λ2 - (3/11)*(λ1 + λ2) + (9/11)]/[( λ2 - λ3)*( λ1 - λ3)]

For any n > 0:

a(n) = (10/11)*3^(n-1) + AP* λ1^(n-1) + BP* λ2^(n-1) + CP* λ3^(n-1)

CROSSREFS

A000244 "Powers of 3" is the sequence (also) describing the number of moves of the k-th disk solving [RED ; BLUE ; BLUE] or [RED ; RED ; BLUE] pre-colored Magnetic Tower of Hanoi.

Cf. A183111 - A183125.

Sequence in context: A004665 A196431 A244826 * A132835 A191354 A001189

Adjacent sequences:  A183108 A183109 A183110 * A183112 A183113 A183114

KEYWORD

nonn,easy

AUTHOR

Uri Levy, Dec 25 2010

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 September 24 04:27 EDT 2017. Contains 292403 sequences.