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 ; BLUE ; NEUTRAL] or [NEUTRAL ; RED ; 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 configurations). Optimal solutions are discussed and their optimality is proved in link 2 listed below.
Number of moves to solve the given puzzle, for large N, is close to 0.5*(10/11)*3^N ~ 0.5*0.909*3^(N). Series designation: S909(N).
REFERENCES
Uri Levy, "The Magnetic Tower of Hanoi", Journal of Recreational Mathematics, Volume 35 Number 3 (2006), 2010, pp 173.
LINKS
U. Levy, The Magnetic Tower of Hanoi, arXiv:1003.0225
Uri Levy, Magnetic Towers of Hanoi and their Optimal Solutions, arXiv:1011.3843
Web applet to play The Magnetic Tower of Hanoi
Index entries for linear recurrences with constant coefficients, signature (4,-2,-2,-5,6).
FORMULA
Recurrence Relations (a(n)=S909(n) as in the referenced papers):
a(n) = a(n-2) + a(n-3) + 3^(n-1) + 3^(n-3) + 2; n >= 3 ; a(0) = 0
Closed-Form Expression:
Define:
λ1 = [1+sqrt(26/27)]^(1/3) + [1-sqrt(26/27)]^(1/3)
λ2 = -0.5* λ1 + 0.5*i*{[sqrt(27)+sqrt(26)]^(1/3)- [sqrt(27)-sqrt(26)]^(1/3)}
λ3 = -0.5* λ1 - 0.5*i*{[sqrt(27)+sqrt(26)]^(1/3)- [sqrt(27)-sqrt(26)]^(1/3)}
AS = [(7/11)* λ2* λ3 - (10/11)*(λ2 + λ3) + (19/11)]/[( λ2 - λ1)*( λ3 - λ1)]
BS = [(7/11)* λ1* λ3 - (10/11)*(λ1 + λ3) + (19/11)]/[( λ1 - λ2)*( λ3 - λ2)]
CS = [(7/11)* λ1* λ2 - (10/11)*(λ1 + λ2) + (19/11)]/[( λ2 - λ3)*( λ1 - λ3)]
For any n > 0:
a(n) = (5/11)*3^n + AS* λ1^(n-1) + BS* λ2^(n-1) + CS* λ3^(n-1) - 1.
G.f.: x*(1-x^2-4*x^3)/((1-x)*(1-3*x)*(1-x^2-2*x^3)); a(n)=4*a(n-1)-2*a(n-2)-2*a(n-3)-5*a(n-4)+6*a(n-5) with n>5. - Bruno Berselli, Dec 29 2010
MATHEMATICA
LinearRecurrence[{4, -2, -2, -5, 6}, {0, 1, 4, 13, 38}, 21] (* Jean-François Alcover, Dec 14 2018 *)
CROSSREFS
A183111 is an "original" sequence describing the number of moves of disk number k, optimally solving the pre-colored puzzle at hand. The integer sequence listed above is the partial sums of the A183111 original sequence.
KEYWORD
nonn
AUTHOR
Uri Levy, Dec 25 2010
STATUS
approved