cp's OEIS Frontend

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

%I A183112 #32 Mar 20 2023 13:41:29
%S A183112 0,1,4,13,38,113,336,1001,2994,8965,26868,80565,241630,724793,2174232,
%T A183112 6522465,19567050,58700621,176101052,528301933,1584903926,4754708929,
%U A183112 14264122464,42792360793,128377072354,385131201813,1155393582212,3466180711333,10398542080270
%N A183112 Magnetic Tower of Hanoi, total number of moves, optimally solving the [RED ; BLUE ; NEUTRAL] or [NEUTRAL ; RED ; BLUE] pre-colored puzzle.
%C A183112 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.
%C A183112 Number of moves to solve the given puzzle, for large N, is close to 0.5*(10/11)*3^N ~ 0.5*0.909*3^(N). Series designation: S909(N).
%D A183112 Uri Levy, "The Magnetic Tower of Hanoi", Journal of Recreational Mathematics, Volume 35 Number 3 (2006),  2010, pp 173.
%H A183112 U. Levy, <a href="http://arxiv.org/abs/1003.0225">The Magnetic Tower of Hanoi</a>, arXiv:1003.0225
%H A183112 Uri Levy, <a href="http://arxiv.org/abs/1011.3843">Magnetic Towers of Hanoi and their Optimal Solutions</a>, arXiv:1011.3843
%H A183112 Web applet <a href="http://www.weizmann.ac.il/zemed/davidson_online/mtoh/MTOHeng.html">to play The Magnetic Tower of Hanoi</a>
%H A183112 <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (4,-2,-2,-5,6).
%F A183112 Recurrence Relations (a(n)=S909(n) as in the referenced papers):
%F A183112 a(n) = a(n-2) + a(n-3) + 3^(n-1) + 3^(n-3) + 2; n >= 3 ; a(0)  = 0
%F A183112 Closed-Form Expression:
%F A183112 Define:
%F A183112 λ1 = [1+sqrt(26/27)]^(1/3) +  [1-sqrt(26/27)]^(1/3)
%F A183112 λ2 = -0.5* λ1 + 0.5*i*{[sqrt(27)+sqrt(26)]^(1/3)- [sqrt(27)-sqrt(26)]^(1/3)}
%F A183112 λ3 = -0.5* λ1 - 0.5*i*{[sqrt(27)+sqrt(26)]^(1/3)- [sqrt(27)-sqrt(26)]^(1/3)}
%F A183112 AS = [(7/11)* λ2* λ3 - (10/11)*(λ2 + λ3) + (19/11)]/[( λ2 - λ1)*( λ3 - λ1)]
%F A183112 BS = [(7/11)* λ1* λ3 - (10/11)*(λ1 + λ3) + (19/11)]/[( λ1 - λ2)*( λ3 - λ2)]
%F A183112 CS = [(7/11)* λ1* λ2 - (10/11)*(λ1 + λ2) + (19/11)]/[( λ2 - λ3)*( λ1 - λ3)]
%F A183112 For any n > 0:
%F A183112 a(n) = (5/11)*3^n + AS* λ1^(n-1) + BS* λ2^(n-1) + CS* λ3^(n-1) - 1.
%F A183112 G.f.: x*(1-x^2-4*x^3)/((1-x)*(1-3*x)*(1-x^2-2*x^3)); a(n)=4*a(n-1)-2*a(n-2)-2*a(n-3)-5*a(n-4)+6*a(n-5) with n>5. - _Bruno Berselli_, Dec 29 2010
%t A183112 LinearRecurrence[{4, -2, -2, -5, 6}, {0, 1, 4, 13, 38}, 21] (* _Jean-François Alcover_, Dec 14 2018 *)
%Y A183112 A183111 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 A183111 original sequence.
%Y A183112 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 A183112 Cf. A183111 - A183125.
%K A183112 nonn
%O A183112 0,3
%A A183112 _Uri Levy_, Dec 25 2010