cp's OEIS Frontend

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

%I A183111 #44 Mar 02 2022 13:23:55
%S A183111 0,1,3,9,25,75,223,665,1993,5971,17903,53697,161065,483163,1449439,
%T A183111 4348233,13044585,39133571,117400431,352200881,1056601993,3169805003,
%U A183111 9509413535,28528238329,85584711561,256754129459,770262380399,2310787129121,6932361368937
%N A183111 Magnetic Tower of Hanoi, number of moves of disk number k, optimally solving the [RED ; BLUE ; NEUTRAL] or [NEUTRAL ; RED ; BLUE] pre-colored puzzle.
%C A183111 A. 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 A183111 B. Disk numbering is from largest disk (k = 1) to smallest disk (k = N)
%C A183111 C. The above-listed "original" sequence generates a "partial-sums" sequence - describing the total number of moves required to solve the puzzle.
%C A183111 D. The number of moves of disk k, for large k, is close to (10/11)*3^(k-1) ~ 0.909*3^(k-1). Series designation: P909(k).
%H A183111 Uri Levy, <a href="http://arxiv.org/abs/1003.0225">The Magnetic Tower of Hanoi</a>, Journal of Recreational Mathematics, Volume 35 Number 3 (2006),  2010, pp 173; arXiv:1003.0225 [math.CO], 2010.
%H A183111 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 A183111 Web applet <a href="http://www.weizmann.ac.il/zemed/davidson_online/mtoh/MTOHeng.html">to play The Magnetic Tower of Hanoi</a>
%H A183111 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (3,1,-1,-6).
%F A183111 G.f.: -x*(-1+4*x^3+x^2) / ( (3*x-1)*(2*x^3+x^2-1) ).
%F A183111 Recurrence Relations (a(n)=P909(n) as in referenced paper):
%F A183111 a(n) = a(n-2) + a(n-3) + 2*3^(n-2) + 2*3^(n-4) ; n >= 4
%F A183111 Closed-Form Expression:
%F A183111 Define:
%F A183111 λ1 = [1+sqrt(26/27)]^(1/3) +  [1-sqrt(26/27)]^(1/3)
%F A183111 λ2 = -0.5* λ1 + 0.5*i*{[sqrt(27)+sqrt(26)]^(1/3)- [sqrt(27)-sqrt(26)]^(1/3)}
%F A183111 λ3 = -0.5* λ1 - 0.5*i*{[sqrt(27)+sqrt(26)]^(1/3)- [sqrt(27)-sqrt(26)]^(1/3)}
%F A183111 AP = [(1/11)* λ2* λ3 - (3/11)*(λ2 + λ3) + (9/11)]/[( λ2 - λ1)*( λ3 - λ1)]
%F A183111 BP = [(1/11)* λ1* λ3 - (3/11)*(λ1 + λ3) + (9/11)]/[( λ1 - λ2)*( λ3 - λ2)]
%F A183111 CP = [(1/11)* λ1* λ2 - (3/11)*(λ1 + λ2) + (9/11)]/[( λ2 - λ3)*( λ1 - λ3)]
%F A183111 For any n > 0:
%F A183111 a(n) = (10/11)*3^(n-1) + AP* λ1^(n-1) + BP* λ2^(n-1) + CP* λ3^(n-1)
%F A183111 33*a(n) = 10*3^n -3*( A052947(n-2) -A052947(n-1) -4*A052947(n) ). - _R. J. Mathar_, Feb 05 2020
%t A183111 LinearRecurrence[{3,1,-1,-6},{0,1,3,9,25},30] (* _Harvey P. Dale_, Apr 30 2018 *)
%Y A183111 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.
%Y A183111 Cf. A183111 - A183125.
%K A183111 nonn,easy
%O A183111 0,3
%A A183111 _Uri Levy_, Dec 25 2010
%E A183111 More terms from _Harvey P. Dale_, Apr 30 2018