%I #15 Jun 13 2015 00:53:41

%S 0,1,3,7,19,53,153,455,1359,4073,12213,36635,109899,329693,989073,

%T 2967215,8901639,26704913,80114733,240344195,721032579,2163097733,

%U 6489293193,19467879575,58403638719,175210916153,525632748453,1576898245355,4730694736059

%N 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.

%C A. 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 B. Disk numbering is from largest disk (k = 1) to smallest disk (k = N)

%C C. The above-listed "original" sequence generates a "partial-sums" sequence - describing the total number of moves required to solve the puzzle.

%C D. Number of moves of disk k, for large k, is close to (67/108)*3^(k-1) ~ 0.62*3^(k-1). Series designation: P62(k).

%D U. Levy, The Magnetic Tower of Hanoi, Journal of Recreational Mathematics, Volume 35 Number 3 (2006), 2010, pp 173.

%H Harvey P. Dale, <a href="/A183122/b183122.txt">Table of n, a(n) for n = 0..1000</a>

%H U. Levy, <a href="http://arxiv.org/abs/1003.0225">The Magnetic Tower of Hanoi</a>, arXiv:1003.0225

%H U. Levy, <a href="http://arxiv.org/abs/1011.3843">Magnetic Towers of Hanoi and their Optimal Solutions</a>, arxiv:1011.3843

%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_03">Index entries for linear recurrences with constant coefficients</a>, signature (3, 1, -3).

%F a(n)=+3*a(n-1)+a(n-2)-3*a(n-3) for n>6.

%F g.f.: x+ 3*x^2 +7*x^3 -x^4*(-19+4*x+25*x^2)/ ((x-1)(3*x-1)(1+x)).

%F (a(n) = P62(n) as in referenced paper):

%F a(n) = 3*a(n-1) - 6; n even; n >= 6

%F a(n) = 3*a(n-1) - 4; n odd; n >= 5

%F a(n) = P67(n-1) + P67(n-2) + P75(n-3) + 8*3^(n-4) ; n >= 4

%F P75(n) and P67(n) refer to the integer sequences described by A122983 and A100702 respectively. See also A183119.

%F a(n) = (67/108)*3^(n-1) + 9/4; n even; n >= 4

%F a(n) = (67/108)*3^(n-1) + 11/4; n odd; n >= 5

%t Join[{0,1,3,7},LinearRecurrence[{3,1,-3},{19,53,153},30]] (* _Harvey P. Dale_, Dec 08 2014 *)

%Y 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 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

%O 0,3

%A _Uri Levy_, Jan 07 2011

%E More terms from _Harvey P. Dale_, Dec 08 2014