A060586 Minimum number of moves required to reach position n starting from 0 in Tower of Hanoi (with three pegs: 0,1,2), where with position n written in base 3, xyz means smallest disk is on peg z, second smallest is on peg y, third smallest on peg x, etc. and leading zeros indicate largest disks are all on peg 0.

0, 1, 1, 3, 3, 2, 3, 2, 3, 7, 6, 7, 6, 7, 7, 5, 5, 4, 7, 7, 6, 5, 4, 5, 6, 7, 7, 15, 15, 14, 13, 12, 13, 14, 15, 15, 12, 13, 13, 15, 15, 14, 15, 14, 15, 11, 10, 11, 10, 11, 11, 9, 9, 8, 15, 14, 15, 14, 15, 15, 13, 13, 12, 11, 11, 10, 9, 8, 9, 10, 11, 11, 12, 13, 13, 15, 15, 14, 15, 14

Offset

0,4

Links

Table of n, a(n) for n=0..79.

Index entries for sequences related to Towers of Hanoi

Formula

a(n) = A060585(A060583(n)).

Example

a(46) = 10 since 46 written in base 3 is 1201 (i.e. with the smallest and fourth smallest disks on the first peg, the third smallest disk on the second peg and the second smallest and any other disks on the zeroth peg) and the optimal moves starting from position 0 go through positions 2, 12, 11, 211, 210, 220, 222, 1222, 1220, 1210 taking ten moves.

Crossrefs

k appears A001316(k) times in the sequence.

Cf. A001511, A055661, A055662.

Sequence in context: A365711 A237347 A075017 * A076662 A164359 A178307

Adjacent sequences: A060583 A060584 A060585 * A060587 A060588 A060589

Keyword

base,nice,nonn

Author

Henry Bottomley, Apr 04 2001

Status

approved