cp's OEIS Frontend

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

%I A183113 #30 Mar 20 2023 13:46:27
%S A183113 0,1,3,7,21,61,179,535,1597,4781,14331,42967,128869,386557,1159587,
%T A183113 3478647,10435757,31306989,93920555,281761015,845282069,2535844733,
%U A183113 7607531923,22822592343,68467771805,205403307437,616209910235,1848629712279,5545889108805
%N A183113 Magnetic Tower of Hanoi, number of moves of disk number k, optimally solving the [RED ; NEUTRAL ; BLUE] pre-colored puzzle.
%C A183113 A.   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 A183113 B.   Disk numbering is from largest disk (k = 1) to smallest disk (k = N)
%C A183113 C.   The above-listed "original" sequence generates a "partial-sums" sequence - describing the total number of moves required to solve the puzzle.
%C A183113 D.   Number of moves of disk k, for large k, is close to (8/11)*3^(k-1) ~ 0.727*3^(k-1). Series designation: P727(k).
%D A183113 Uri Levy, "The Magnetic Tower of Hanoi", Journal of Recreational Mathematics, Volume 35 Number 3 (2006), 2010, pp 173.
%H A183113 1. <a href="http://arxiv.org/abs/1003.0225">The Magnetic Tower of Hanoi</a>, Uri Levy
%H A183113 2. <a href="http://arxiv.org/abs/1011.3843">Magnetic Towers of Hanoi and their Optimal Solutions</a>, Uri Levy
%H A183113 3. Web applet <a href="http://www.weizmann.ac.il/zemed/davidson_online/mtoh/MTOHeng.html">to play The Magnetic Tower of Hanoi</a>
%H A183113 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (3,1,-1,-6).
%F A183113 Recurrence Relations (a(n)=P727(n) as in referenced paper):
%F A183113 P727(k) = P727(k-2) + 2*P727(k-3) + 4*3^(k-3) + 4*3^(k-4) ; k >= 4
%F A183113 Closed-Form Expression:
%F A183113 Define:
%F A183113 λ1 = [1+sqrt(26/27)]^(1/3) +  [1-sqrt(26/27)]^(1/3)
%F A183113 λ2 = -0.5* λ1 + 0.5*i*{[sqrt(27)+sqrt(26)]^(1/3)- [sqrt(27)-sqrt(26)]^(1/3)}
%F A183113 λ3 = -0.5* λ1 - 0.5*i*{[sqrt(27)+sqrt(26)]^(1/3)- [sqrt(27)-sqrt(26)]^(1/3)}
%F A183113 AP = [(1/11)* λ2* λ3 - (3/11)*(λ2 + λ3) + (9/11)]/[( λ2 - λ1)*( λ3 - λ1)]
%F A183113 BP = [(1/11)* λ1* λ3 - (3/11)*(λ1 + λ3) + (9/11)]/[( λ1 - λ2)*( λ3 - λ2)]
%F A183113 CP = [(1/11)* λ1* λ2 - (3/11)*(λ1 + λ2) + (9/11)]/[( λ2 - λ3)*( λ1 - λ3)]
%F A183113 For any k > 0:
%F A183113 P727(n) = (8/11)*3^(n-1) + AP* λ1^n + BP* λ2^n + CP* λ3^n.
%F A183113 G.f.: x*(1-2*x)*(1+x)^2/((1-3*x)*(1-x^2-2*x^3)); a(n) = 3*a(n-1)+a(n-2)-a(n-3)-6*a(n-4) with n>4. - _Bruno Berselli_, Dec 29 2010
%t A183113 Join[{0},LinearRecurrence[{3,1,-1,-6},{1,3,7,21},40]] (* or *) CoefficientList[ Series[ x(1-2x)(1+x)^2/((1-3x)(1-x^2-2x^3)),{x,0,40}],x] (* _Harvey P. Dale_, May 11 2011 *)
%Y A183113 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 A183113 A183111 through A183125 are related sequences, all associated with various solutions of the pre-coloring variations of the Magnetic Tower of Hanoi.
%K A183113 nonn
%O A183113 0,3
%A A183113 _Uri Levy_, Dec 28 2010
%E A183113 More terms from _Harvey P. Dale_, May 11 2011