OFFSET
0,3
COMMENTS
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.
Large N limit of the sequence is 0.5*(3/4)*3^N = 0.5*0.75*3^N. Series designation: S75(n).
REFERENCES
Uri Levy, The Magnetic Tower of Hanoi, Journal of Recreational Mathematics, Volume 35 Number 3 (2006), 2010, pp 173.
LINKS
Muniru A Asiru, Table of n, a(n) for n = 0..2070
Uri Levy, The Magnetic Tower of Hanoi, arXiv:1003.0225 [math.CO], 2010.
Uri Levy, Magnetic Towers of Hanoi and their Optimal Solutions, arXiv:1011.3843 [math.CO], 2010.
Uri Levy, to play The Magnetic Tower of Hanoi, web applet [Broken link]
Index entries for linear recurrences with constant coefficients, signature (4,-2,-4,3).
FORMULA
G.f.: x*(-1+3*x^2) / ( (1+x)*(3*x-1)*(x-1)^2 ).
(a(n)=S75(n) in referenced paper):
a(n) = 3*a(n-1) - n + 3; n even; n >= 2
a(n) = 3*a(n-1) - n + 2; n odd; n >= 1
a(n) = a(n-2) + 3^(n-1) + 1; n >= 2
a(n) = 3^(n+1)/8 + (n-1)/2 +(-1)^n/8.
MAPLE
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
MATHEMATICA
LinearRecurrence[{4, -2, -4, 3}, {0, 1, 4, 11}, 30] (* Jean-François Alcover, Dec 04 2018 *)
Table[3^(n + 1) / 8 + (n - 1) / 2 + (-1)^n / 8, {n, 0, 30}] (* Vincenzo Librandi, Dec 04 2018 *)
PROG
(PARI) a(n) = 3^(n+1)/8 + (n-1)/2 + (-1)^n/8 \\ Charles R Greathouse IV, Jun 11 2015
(Magma) [3^(n+1)/8+(n-1)/2+(-1)^n/8: n in [0..30]]; // Vincenzo Librandi, Dec 04 2018
CROSSREFS
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.
KEYWORD
nonn,easy
AUTHOR
Uri Levy, Jan 03 2011
EXTENSIONS
More terms from Jean-François Alcover, Dec 04 2018
STATUS
approved