cp's OEIS Frontend

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

%I A183114 #24 Sep 08 2022 08:45:55
%S A183114 0,1,4,11,32,93,272,807,2404,7185,21516,64483,193352,579909,1739496,
%T A183114 5218143,15653900,46960889,140881444,422642459,1267924528,3803769261,
%U A183114 11411301184,34233893527,102701665332,308104972769,924314883004,2772944595283,8318833704088,24956500987925
%N A183114 Magnetic Tower of Hanoi, total number of moves, optimally solving the [RED ; NEUTRAL ; BLUE] pre-colored puzzle.
%C A183114 The Magnetic Tower of Hanoi puzzle is described in link 1 listed below. The Magnetic Tower is pre-colored. Pre-coloring is [RED ; 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 configuration). Optimal solutions are discussed and their optimality is proved in link 2 listed below.
%C A183114 Number of moves to solve the given puzzle, for large N, is close to 0.5*(8/11)*3^N ~ 0.5*0.727*3^(N). Series designation: S727(N).
%D A183114 U. Levy, The Magnetic Tower of Hanoi, Journal of Recreational Mathematics, Volume 35 Number 3 (2006), 2010, pp 173.
%H A183114 Muniru A Asiru, <a href="/A183114/b183114.txt">Table of n, a(n) for n = 0..2030</a>
%H A183114 U. Levy, <a href="http://arxiv.org/abs/1003.0225">The Magnetic Tower of Hanoi</a>, arXiv:1003.0225 [math.CO], 2010.
%H A183114 U. 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 A183114 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]
%H A183114 <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (4,-2,-2,-5,6).
%F A183114 G.f.: x*(2*x-1)*(1+x)^2 / ( (x-1)*(3*x-1)*(2*x^3+x^2-1) ).
%F A183114 Recurrence Relations (a(n)=S727(n) as in referenced paper):
%F A183114 a(N) = a(N-2) + 2*a(N-3) + 8*3^(N-3) + 2 ; N ≥ 3 ; S727(0)  = 0
%F A183114 Closed-Form Expression:
%F A183114 Define:
%F A183114 λ1 = [1+sqrt(26/27)]^(1/3) +  [1-sqrt(26/27)]^(1/3)
%F A183114 λ2 = -0.5* λ1 + 0.5*i*{[sqrt(27)+sqrt(26)]^(1/3)- [sqrt(27)-sqrt(26)]^(1/3)}
%F A183114 λ3 = -0.5* λ1 - 0.5*i*{[sqrt(27)+sqrt(26)]^(1/3)- [sqrt(27)-sqrt(26)]^(1/3)}
%F A183114 AS = [(7/11)* λ2* λ3 - (10/11)*(λ2 + λ3) + (19/11)]/[( λ2 - λ1)*( λ3 - λ1)]
%F A183114 BS = [(7/11)* λ1* λ3 - (10/11)*(λ1 + λ3) + (19/11)]/[( λ1 - λ2)*( λ3 - λ2)]
%F A183114 CS = [(7/11)* λ1* λ2 - (10/11)*(λ1 + λ2) + (19/11)]/[( λ2 - λ3)*( λ1 - λ3)]
%F A183114 For any N > 0:
%F A183114 a(N) = (4/11)*3^N + AS* λ1^N + BS* λ2^N + CS* λ3^N - 1
%F A183114 a(n) = 4*a(n-1)-2*a(n-2)-2*a(n-3)-5*a(n-4)+6*a(n-5). - _Vincenzo Librandi_, Dec 04 2018
%p A183114 seq(coeff(series(x*(2*x-1)*(1+x)^2/((x-1)*(3*x-1)*(2*x^3+x^2-1)),x,n+1), x, n), n = 0 .. 35); # _Muniru A Asiru_, Dec 04 2018
%t A183114 LinearRecurrence[{4, -2, -2, -5, 6}, {0, 1, 4, 11, 32}, 30] (* _Jean-François Alcover_, Dec 04 2018 *)
%t A183114 CoefficientList[Series[x (2 x - 1) (1 + x)^2 / ((x - 1) (3 x - 1) (2 x^3 + x^2 - 1)), {x, 0, 33}], x] (* _Vincenzo Librandi_, Dec 04 2018 *)
%o A183114 (Magma) I:=[0,1,4,11,32]; [n le 5 select I[n] else 4*Self(n-1)-2*Self(n-2)-2*Self(n-3)-5*Self(n-4)+6*Self(n-5): n in [1..30]]; // _Vincenzo Librandi_, Dec 04 2018
%Y A183114 A183113 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 A183113 original sequence.
%Y A183114 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 A183114 Cf. A183111 - A183125.
%K A183114 nonn
%O A183114 0,3
%A A183114 _Uri Levy_, Dec 29 2010
%E A183114 More terms from _Jean-François Alcover_, Dec 04 2018