|
%I #27 Sep 08 2022 08:45:55
%S 0,1,4,11,32,93,276,823,2464,7385,22148,66435,199296,597877,1793620,
%T 5380847,16142528,48427569,145282692,435848059,1307544160,3922632461,
%U 11767897364,35303692071,105911076192,317733228553,953199685636,2859599056883,8578797170624,25736391511845
%N Magnetic Tower of Hanoi, total number of moves generated by a certain algorithm, yielding a "forward moving" non-optimal solution of the [RED ; NEUTRAL ; 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 ; NEUTRAL ; BLUE], given in [Source ; Intermediate ; Destination] order. The solution algorithm producing the presented sequence is NOT optimal. The particular "75" algorithm solving the puzzle at hand is presented in a paper referenced by link 1 listed below. For the optimal solution of the Magnetic Tower of Hanoi puzzle with the given pre-coloring configuration see A183113 and A183114. Optimal solutions are discussed and their optimality is proved in link 2 listed below.
%C Large N limit of the sequence is 0.5*(3/4)*3^N = 0.5*0.75*3^N. Series designation: S75(n).
%D Uri Levy, The Magnetic Tower of Hanoi, Journal of Recreational Mathematics, Volume 35 Number 3 (2006), 2010, pp 173.
%H Muniru A Asiru, <a href="/A183119/b183119.txt">Table of n, a(n) for n = 0..2070</a>
%H Uri Levy, <a href="http://arxiv.org/abs/1003.0225">The Magnetic Tower of Hanoi</a>, arXiv:1003.0225 [math.CO], 2010.
%H 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 Uri Levy, <a href="http://www.weizmann.ac.il/zemed/davidson_online/mtoh/MTOHeng.html">to play The Magnetic Tower of Hanoi</a>, web applet [Broken link]
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (4,-2,-4,3).
%F G.f.: x*(-1+3*x^2) / ( (1+x)*(3*x-1)*(x-1)^2 ).
%F (a(n)=S75(n) in referenced paper):
%F a(n) = 3*a(n-1) - n + 3; n even; n >= 2
%F a(n) = 3*a(n-1) - n + 2; n odd; n >= 1
%F a(n) = a(n-2) + 3^(n-1) + 1; n >= 2
%F a(n) = 3^(n+1)/8 + (n-1)/2 +(-1)^n/8.
%p seq(coeff(series(x*(3*x^2-1)/((1+x)*(3*x-1)*(x-1)^2),x,n+1), x, n), n = 0 .. 30); # _Muniru A Asiru_, Dec 04 2018
%t LinearRecurrence[{4, -2, -4, 3}, {0, 1, 4, 11}, 30] (* _Jean-François Alcover_, Dec 04 2018 *)
%t Table[3^(n + 1) / 8 + (n - 1) / 2 + (-1)^n / 8, {n, 0, 30}] (* _Vincenzo Librandi_, Dec 04 2018 *)
%o (PARI) a(n) = 3^(n+1)/8 + (n-1)/2 + (-1)^n/8 \\ _Charles R Greathouse IV_, Jun 11 2015
%o (Magma) [3^(n+1)/8+(n-1)/2+(-1)^n/8: n in [0..30]]; // _Vincenzo Librandi_, Dec 04 2018
%Y A122983 - "Binomial transform of aeration of A081294" is an "original" sequence (also) describing the number of moves of disk number k, solving the pre-colored puzzle at hand when executing the "75" algorithm mentioned above and presented in the paper referenced by link 1 above. The integer sequence listed above is the partial sums of the A122983 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,easy
%O 0,3
%A _Uri Levy_, Jan 03 2011
%E More terms from _Jean-François Alcover_, Dec 04 2018
| 