Notation first: Since many formulas will be of this form, let (a, b, c) denote the expression (a * 4^n + b)/3 + c*n. I shall refer to moves by the pin the disk is taken from followed by the pin it goes to. So the solution to normal tower of hanoi with 3 disks in this notation is 02.01.21.02.10.12.02.

To move a disk of a particular size, it is necessary for all disks of lower size to be stacked up in a pile. Let the number of moves necessary to move such a pile with 2n disks in it from one pin to another be T_n. From the solution to the standard hanoi problem, we have T_n = 2^(n+1) - 2. That is:

T_2n = (6, -6, 0)
T_(2n - 1) = (3, -6, 0)

It is also worthwhile to see how long it takes to form such a tower. Such a tower may (when first formed) be on pin 2: let the minimal number of moves to reach this situation be B_n. Let the minimal number of moves to reach the other such situation (the tower on top of a stack on pin 1 or 2) be A_n. By induction on n, you may obtain:

A_2n = (8, -8, -3)
A_(2n-1) = (4, -4, -3)
B_2n = (10, -10, -3)
B_(2n-1) = (5, -5, -3)

Finally, cosider the final two layers together with the tower above them. It is necessary to swap the bases, get the next two the right way around, and do this moving the tower as little as possible. The best solution (8 tower moves, 11 other moves) also saves a little time by finishing with the tower in position A, since A_k is in general less than B_k. The sequence, starting with the tower on place 0 and considering the tower as a single object, is:

12.02.01.20.21.01.02.10.12.12.02.10.21.20.20.10.21.02.01

Handily, now that the bottom two layers are right there is no more need to worry: The other layers may be arranged as we wish. So the least number of moves for towers with n disks is L_n, satisfying L_n = A_(n-2) + B_(n-2) + 8*T_(n-2) + 11. That is:

L_(2n+2) = (66, -33, -6) = 11*(2^(2n+1) - 1) - 3*2n
L_(2n+1) = (33, -24, -6) = 11*(2^(2n) - 1) - 3*(2n-1)

These two are the same: L_k = 11*(2^(k-1) - 1) - 3(k-2) for k sufficiently large. Of course, for n <= 2 the values are different: L_0 = 0, L_1 = 3, L_2 = 10. However, it'suggests there is a nicer way to get the formula, but I don't know it. It gives an answer of 11*3 - 3 = 30 for k = 3 (the string is 10.12.02.02.01.20.20.21.01.01.02.10.10.12.12.02.02.10.21.21.20.20.10.10.21.02.02.01.20.21). Is that right? Anyway, if you generalised the problem any more it would be hard to get exact values, just upper and lower bounds. What sort of generalisation were you after?

Thankyou

sfwc
<><

That's good enough. I think this is clear from the context too.

>So here is my solution to n-disk
>bicolor tower of hanoi:

With your permission, I'll move this to the main site. More people will see this.