A183112 - OEIS

%I #32 Mar 20 2023 13:41:29

%S 0,1,4,13,38,113,336,1001,2994,8965,26868,80565,241630,724793,2174232,

%T 6522465,19567050,58700621,176101052,528301933,1584903926,4754708929,

%U 14264122464,42792360793,128377072354,385131201813,1155393582212,3466180711333,10398542080270

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

%C 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 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 Uri Levy, "The Magnetic Tower of Hanoi", Journal of Recreational Mathematics, Volume 35 Number 3 (2006),  2010, pp 173.

%H U. Levy, <a href="http://arxiv.org/abs/1003.0225">The Magnetic Tower of Hanoi</a>, arXiv:1003.0225

%H Uri Levy, <a href="http://arxiv.org/abs/1011.3843">Magnetic Towers of Hanoi and their Optimal Solutions</a>, arXiv:1011.3843

%H Web applet <a href="http://www.weizmann.ac.il/zemed/davidson_online/mtoh/MTOHeng.html">to play The Magnetic Tower of Hanoi</a>

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (4,-2,-2,-5,6).

%F Recurrence Relations (a(n)=S909(n) as in the referenced papers):

%F a(n) = a(n-2) + a(n-3) + 3^(n-1) + 3^(n-3) + 2; n >= 3 ; a(0)  = 0

%F Closed-Form Expression:

%F Define:

%F λ1 = [1+sqrt(26/27)]^(1/3) +  [1-sqrt(26/27)]^(1/3)

%F λ2 = -0.5* λ1 + 0.5*i*{[sqrt(27)+sqrt(26)]^(1/3)- [sqrt(27)-sqrt(26)]^(1/3)}

%F λ3 = -0.5* λ1 - 0.5*i*{[sqrt(27)+sqrt(26)]^(1/3)- [sqrt(27)-sqrt(26)]^(1/3)}

%F AS = [(7/11)* λ2* λ3 - (10/11)*(λ2 + λ3) + (19/11)]/[( λ2 - λ1)*( λ3 - λ1)]

%F BS = [(7/11)* λ1* λ3 - (10/11)*(λ1 + λ3) + (19/11)]/[( λ1 - λ2)*( λ3 - λ2)]

%F CS = [(7/11)* λ1* λ2 - (10/11)*(λ1 + λ2) + (19/11)]/[( λ2 - λ3)*( λ1 - λ3)]

%F For any n > 0:

%F a(n) = (5/11)*3^n + AS* λ1^(n-1) + BS* λ2^(n-1) + CS* λ3^(n-1) - 1.

%F 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 LinearRecurrence[{4, -2, -2, -5, 6}, {0, 1, 4, 13, 38}, 21] (* _Jean-François Alcover_, Dec 14 2018 *)

%Y 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 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 Cf. A183111 - A183125.

%K nonn

%O 0,3

%A _Uri Levy_, Dec 25 2010