%I #24 May 06 2024 01:45:25
%S 0,1,4,11,30,83,236,691,2050,6123,18336,54971,164870,494563,1483636,
%T 4450851,13352490,40057403,120172136,360516331,1081548910,3244646643,
%U 9733939836,29201819411,87605458130,262816374283,788449122736,2365347368091,7096042104150
%N Magnetic Tower of Hanoi, total number of moves, generated by a certain algorithm, yielding a "forward moving" non-optimal solution of the [NEUTRAL ; NEUTRAL ; NEUTRAL] 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 [NEUTRAL ; NEUTRAL ; NEUTRAL], given in [Source ; Intermediate ; Destination] order. The solution algorithm producing the presented sequence is NOT optimal. The particular "62" algorithm solving the puzzle at hand is presented and discussed in the paper referenced by link 1 below. For the optimal solution of the Magnetic Tower of Hanoi puzzle with the given pre-coloring configuration (the "natural" or "free" Magnetic Tower) see A183117 and A183118. Optimal solutions are discussed and their optimality is proved in link 2 listed below.
%C Large N limit of the sequence is 0.5*(67/108)*3^N ~ 0.5*0.62*3^N. Series designation: S62(n).
%D U. 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 [math.CO], 2010.
%H 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 U. Levy, <a href="http://www.weizmann.ac.il/zemed/davidson_online/mtoh/MTOHeng.html">to play The Magnetic Tower of Hanoi</a>, web applet.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (4,-2,-4,3).
%F a(n)=+4*a(n-1)-2*a(n-2)-4*a(n-3)+3*a(n-4) for n>6.
%F (a(n) = S62(n) as in referenced paper):
%F S62(n) = 3*S62(n-1) - 5*n + 17; n even; n >= 4
%F S62(n) = 3*S62(n-1) - 5*n + 13; n odd; n >= 5
%F S62(n) = S67(n-1) + S67(n-2) + S75(n-3) + 4*3^(n-3) + 2; n >= 3
%F S67(n) and S75(n) refer to the integer sequences described by A104743 and A183119 respectively.
%F S62(n) = 0.5*(67/108)*3^n + 2.5*n - 41/8; n even; n >= 4
%F S62(n) = 0.5*(67/108)*3^n + 2.5*n - 39/8; n odd; n >= 3.
%F a(n) = -5-(-1)^n/8+(67*3^(-3+n))/8+(5*n)/2 for n>2. - _Colin Barker_, Sep 18 2014
%F G.f.: x*(4*x^5+2*x^4+2*x^3+3*x^2-1) / ((x-1)^2*(x+1)*(3*x-1)). - _Colin Barker_, Sep 18 2014
%t LinearRecurrence[{4,-2,-4,3},{0,1,4,11,30,83,236},40] (* _Harvey P. Dale_, Jun 07 2015 *)
%o (PARI) concat(0, Vec(x*(4*x^5+2*x^4+2*x^3+3*x^2-1)/((x-1)^2*(x+1)*(3*x-1)) + O(x^100))) \\ _Colin Barker_, Sep 18 2014
%Y Cf. A183122 - "Magnetic Tower of Hanoi, number of moves of disk number k, generated by a certain algorithm, yielding a "forward moving" non-optimal solution of the [NEUTRAL ; NEUTRAL ; NEUTRAL] pre-colored puzzle" is an "original" sequence describing the number of moves of disk number k, solving the pre-colored puzzle at hand when executing the "62" algorithm mentioned above.
%Y Cf. 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. A183111 through A183125 are related sequences, all associated with various solutions of the pre-coloring variations of the Magnetic Tower of Hanoi.
%K nonn,easy
%O 0,3
%A _Uri Levy_, Jan 07 2011
%E More terms and correction to recurrence by _Colin Barker_, Sep 18 2014