cp's OEIS Frontend

A183116 Magnetic Tower of Hanoi, total number of moves, optimally solving the [RED ; NEUTRAL ; NEUTRAL] or [NEUTRAL ; NEUTRAL ; BLUE] pre-colored puzzle.

%I A183116 #15 Jan 30 2019 03:19:48
%S A183116 0,1,4,11,30,85,244,715,2118,6309,18860,56475,169262,507541,1522244,
%T A183116 4566155,13697590,41091429,123272252,369813659,1109436254
%N A183116 Magnetic Tower of Hanoi, total number of moves, optimally solving the [RED ; NEUTRAL ; NEUTRAL] or [NEUTRAL ; NEUTRAL ; BLUE] pre-colored puzzle.
%C A183116 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.
%C A183116 Number of moves to solve the given puzzle, for large N, is close to 0.5*(7/11)*3^N ~ 0.5*0.636*3^(N). Series designation: S636(N).
%D A183116 "The Magnetic Tower of Hanoi", Uri Levy, Journal of Recreational Mathematics, Volume 35 Number 3 (2006), 2010, pp 173.
%H A183116 Uri Levy, <a href="http://arxiv.org/abs/1003.0225">The Magnetic Tower of Hanoi</a>, arxiv:1003.0225 [math.CO], 2010.
%H A183116 Uri Levy, <a href="http://arxiv.org/abs/1011.3843">Magnetic Towers of Hanoi and their Optimal Solutions</a>, arXiv:1011.3843 [math.CO], 2010.
%H A183116 Uri Levy, <a href="http://www.weizmann.ac.il/zemed/davidson_online/mtoh/MTOHeng.html">to play The Magnetic Tower of Hanoi</a>, Web Applet. [Broken link]
%F A183116 G.f. appears to be (-4*x^3-3*x^2+1)/(-6*x^5+5*x^4+2*x^3+2*x^2-4*x+1).
%F A183116 Recurrence Relations (a(n)=S636(n) as in referenced paper):
%F A183116 S636(n) = S636(n-1) + 2*S909(n-2) + 3^(n-2) + 2 ; n >= 2 ; S909(0)  = 0
%F A183116 Note:  S909(n-2) refers to the integer sequence described by A183112.
%F A183116 Closed-Form Expression:
%F A183116 Define:
%F A183116 λ1 = [1+sqrt(26/27)]^(1/3) +  [1-sqrt(26/27)]^(1/3)
%F A183116 λ2 = -0.5* λ1 + 0.5*i*{[sqrt(27)+sqrt(26)]^(1/3)- [sqrt(27)-sqrt(26)]^(1/3)}
%F A183116 λ3 = -0.5* λ1 - 0.5*i*{[sqrt(27)+sqrt(26)]^(1/3)- [sqrt(27)-sqrt(26)]^(1/3)}
%F A183116 AS = [(7/11)* λ2* λ3 - (10/11)*(λ2 + λ3) + (19/11)]/[( λ2 - λ1)*( λ3 - λ1)]
%F A183116 BS = [(7/11)* λ1* λ3 - (10/11)*(λ1 + λ3) + (19/11)]/[( λ1 - λ2)*( λ3 - λ2)]
%F A183116 CS = [(7/11)* λ1* λ2 - (10/11)*(λ1 + λ2) + (19/11)]/[( λ2 - λ3)*( λ1 - λ3)]
%F A183116 For n > 0:
%F A183116 S636(n) = (7/22)*3^n + AS*(λ1 + 1)*λ1^(n-1) + BS*(λ2 + 1)*λ2^(n-1) + CS*(λ3 + 1)*λ3^(n-1) - (3/2)
%t A183116 L1 = Root[-2 - # + #^3&, 1];
%t A183116 L2 = Root[-2 - # + #^3&, 3];
%t A183116 L3 = Root[-2 - # + #^3&, 2];
%t A183116 AP = Root[-2 - 9 # - 52 #^2 + 572 #^3&, 1];
%t A183116 BP = Root[-2 - 9 # - 52 #^2 + 572 #^3&, 3];
%t A183116 CP = Root[-2 - 9 # - 52 #^2 + 572 #^3&, 2];
%t A183116 (* b = A183115 *) b[0] = 0; b[n_] := (7/11) 3^(n-1) + AP (L1+1) L1^(n-1) + BP (L2+1) L2^(n-1) + CP (L3+1) L3^(n-1) // Round;
%t A183116 Array[b, 21, 0] // Accumulate (* _Jean-François Alcover_, Jan 30 2019 *)
%Y A183116 A183115 is an "original" sequence describing the number of moves of disk number k, optimally solving the pre-colored puzzle at hand. The integer sequence listed above is the partial sums of the A183115 original sequence.
%Y A183116 A003462 "Partial sums of A000244" is the sequence (also) describing the total number of moves solving [RED ; BLUE ; BLUE] or [RED ; RED ; BLUE] pre-colored Magnetic Tower of Hanoi puzzle.
%Y A183116 A183111 through A183125 are related sequences, all associated with various solutions of the pre-coloring variations of the Magnetic Tower of Hanoi.
%K A183116 nonn
%O A183116 0,3
%A A183116 _Uri Levy_, Dec 31 2010