cp's OEIS Frontend

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.

%I A183115 #29 Aug 21 2025 07:01:04
%S A183115 0,1,3,7,19,55,159,471,1403,4191,12551,37615,112787,338279,1014703,
%T A183115 3043911,9131435,27393839,82180823,246541407,739622595,2218865335,
%U A183115 6656592255,19969771063,59909304539,179727900415,539183681191,1617551013071,4852652992755,14557958907655,43673876615503
%N 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.
%C A183115 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 A183115 Disk numbering is from largest disk (k = 1) to smallest disk (k = N)
%C A183115 The above-listed "original" sequence generates a "partial-sums" sequence - describing the total number of moves required to solve the puzzle.
%C A183115 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).
%D A183115 Uri Levy, "The Magnetic Tower of Hanoi", Journal of Recreational Mathematics, Volume 35 Number 3 (2006), 2010, pp. 173.
%H A183115 Uri Levy, <a href="http://arxiv.org/abs/1003.0225">The Magnetic Tower of Hanoi</a>, arXiv:1003.0225 [math.CO], 2010.
%H A183115 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 A183115 Web applet <a href="http://www.weizmann.ac.il/zemed/davidson_online/mtoh/MTOHeng.html">to play The Magnetic Tower of Hanoi</a> [Broken link]
%F A183115 Recurrence Relations (a(n)=P636(n) as in referenced paper):
%F A183115 P636(n) = P636(n-1) + 2*P909(n-2) + 2*3^(n-3) ; n >= 3
%F A183115 Note:  P909(n-2) refers to the integer sequence described by A183111.
%F A183115 Closed-Form Expression:
%F A183115 Define:
%F A183115 λ1 = [1+sqrt(26/27)]^(1/3) +  [1-sqrt(26/27)]^(1/3)
%F A183115 λ2 = -0.5* λ1 + 0.5*i*{[sqrt(27)+sqrt(26)]^(1/3)- [sqrt(27)-sqrt(26)]^(1/3)}
%F A183115 λ3 = -0.5* λ1 - 0.5*i*{[sqrt(27)+sqrt(26)]^(1/3)- [sqrt(27)-sqrt(26)]^(1/3)}
%F A183115 AP = [(1/11)* λ2* λ3 - (3/11)*(λ2 + λ3) + (9/11)]/[( λ2 - λ1)*( λ3 - λ1)]
%F A183115 BP = [(1/11)* λ1* λ3 - (3/11)*(λ1 + λ3) + (9/11)]/[( λ1 - λ2)*( λ3 - λ2)]
%F A183115 CP = [(1/11)* λ1* λ2 - (3/11)*(λ1 + λ2) + (9/11)]/[( λ2 - λ3)*( λ1 - λ3)]
%F A183115 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)
%F A183115 G.f.: x*(1-3*x^2-4*x^3)/((1-3*x)*(1-x^2-2*x^3)). - _Colin Barker_, Jan 12 2012
%t A183115 L1 = Root[-2 - # + #^3&, 1];
%t A183115 L2 = Root[-2 - # + #^3&, 3];
%t A183115 L3 = Root[-2 - # + #^3&, 2];
%t A183115 AP = Root[-2 - 9 # - 52 #^2 + 572 #^3&, 1];
%t A183115 BP = Root[-2 - 9 # - 52 #^2 + 572 #^3&, 3];
%t A183115 CP = Root[-2 - 9 # - 52 #^2 + 572 #^3&, 2];
%t A183115 a[0] = 0;
%t A183115 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);
%t A183115 Table[a[n] // Round, {n, 0, 30}] (* _Jean-François Alcover_, Dec 03 2018 *)
%Y A183115 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.
%Y A183115 A183111 through A183125 are related sequences, all associated with various solutions of the pre-coloring variations of the Magnetic Tower of Hanoi.
%K A183115 nonn
%O A183115 0,3
%A A183115 _Uri Levy_, Dec 31 2010
%E A183115 More terms from _Jean-François Alcover_, Dec 03 2018