login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A183115 Magnetic Tower of Hanoi, number of moves of disk number k, optimally solving the [RED ; NEUTRAL ; NEUTRAL] or [NEUTRAL ; NEUTRAL ; BLUE] pre-colored puzzle. 4
0, 1, 3, 7, 19, 55, 159, 471, 1403, 4191, 12551, 37615, 112787, 338279, 1014703, 3043911, 9131435, 27393839, 82180823, 246541407, 739622595, 2218865335, 6656592255, 19969771063, 59909304539, 179727900415, 539183681191, 1617551013071, 4852652992755, 14557958907655, 43673876615503 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

The Magnetic Tower of Hanoi puzzle is described in link 1 listed below. The Magnetic Tower is pre-colored. Pre-coloring is [RED ; NEUTRAL ; NEUTRAL] or [NEUTRAL ; NEUTRAL ; 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.

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

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

Number of moves of disk k, for large k,  is close to (7/11)*3^(k-1) ~ 0.636*3^(k-1). Series designation: P636(k).

REFERENCES

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

LINKS

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

Uri Levy, The Magnetic Tower of Hanoi, arXiv:1003.0225 [math.CO], 2010.

Uri Levy, Magnetic Towers of Hanoi and their Optimal Solutions, arXiv:1011.3843 [math.CO], 2010.

Web applet to play The Magnetic Tower of Hanoi [Broken link]

FORMULA

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

P636(n) = P636(n-1) + 2*P909(n-2) + 2*3^(n-3) ; n >= 3

Note:  P909(n-2) refers to the integer sequence described by A183111.

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 n > 0:

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

Empirical G.f.: x*(1-3*x^2-4*x^3)/((1-3*x)*(1-x^2-2*x^3)). [Colin Barker, Jan 12 2012]

MATHEMATICA

L1 = Root[-2 - # + #^3&, 1];

L2 = Root[-2 - # + #^3&, 3];

L3 = Root[-2 - # + #^3&, 2];

AP = Root[-2 - 9 # - 52 #^2 + 572 #^3&, 1];

BP = Root[-2 - 9 # - 52 #^2 + 572 #^3&, 3];

CP = Root[-2 - 9 # - 52 #^2 + 572 #^3&, 2];

a[0] = 0;

a[n_] := (7/11) 3^(n-1) + AP (L1+1) L1^(n-1) + BP (L2+1) L2^(n-1) + CP (L3+1) L3^(n-1);

Table[a[n] // Round, {n, 0, 30}] (* Jean-François Alcover, Dec 03 2018 *)

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 puzzle.

A183111 through A183125 are related sequences, all associated with various solutions of the pre-coloring variations of the Magnetic Tower of Hanoi.

Sequence in context: A104522 A175533 A115760 * A183120 A100702 A224031

Adjacent sequences:  A183112 A183113 A183114 * A183116 A183117 A183118

KEYWORD

nonn

AUTHOR

Uri Levy, Dec 31 2010

EXTENSIONS

More terms from Jean-François Alcover, Dec 03 2018

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 15 01:56 EDT 2020. Contains 336485 sequences. (Running on oeis4.)