A290187 Minimum number of moves to rearrange a Tower of Hanoi puzzle with 3 colors. There are 3 rods with n discs in descending sizes. On the first rod there are n red discs, on the 2nd n blue discs and on the 3rd n white ones.

5, 23, 68, 168, 377, 801, 1657, 3377, 6825, 13729, 27545, 55185

Offset

1,1

Comments

Like the known Tower of Hanoi you have 3 rods with n discs in descending sizes. But here on the first rod there are n red discs, on the 2nd n blue discs and on the 3rd n white ones.

The task is to rearrange the discs so that red ones go to rod 2, the blue ones to rod 3 and the white ones to rod 1. Sequence lists the number of minimum moves needed to rearrange the discs.

I have written a program to find the minimum moves, it might be improved for higher values.

Links

Table of n, a(n) for n=1..12.

Cut The Knot, 3-Colors Tower of Hanoi

Bodo Zinser, Tower of Hanoi with three colors (explanation of the algorithm)

Index entries for sequences related to Towers of Hanoi

Example

For n=1 the moves are 23-12-32-31-23 (meaning to move a disc from rod 2 to 3, then 1 to 2, ...).
For n=2 the moves are 31-21-23-13-13-13-12-31-31-31-32-12-12-12-31-21-21-21-23-13-13-12-31.

Crossrefs

Cf. A000225, A055622 (another 3-color variant of the Towers of Hanoi).

Sequence in context: A106956 A084671 A284648 * A243442 A064395 A230497

Adjacent sequences: A290184 A290185 A290186 * A290188 A290189 A290190

Keyword

nonn,more

Author

Bodo Zinser, Jul 23 2017

Status

approved