A055661 -id:A055661 - cp's OEIS frontend

A055662 Successive positions in Tower of Hanoi (with three pegs {0,1,2}) where 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, 21, 22, 122, 120, 110, 111, 2111, 2112, 2102, 2100, 2200, 2201, 2221, 2222, 12222, 12220, 12210, 12211, 12011, 12012, 12002, 12000, 11000, 11001, 11021, 11022, 11122, 11120, 11110, 11111, 211111, 211112, 211102, 211100, 211200

Offset: 0

Henry Bottomley, Jun 06 2000

nonn

Optimal for moving an even number of disks from peg 0 to peg 2 or an odd number from peg 0 to peg 1.

Index entries for sequences related to Towers of Hanoi

Cf. A001511, A055661.

Cf. A060572.

a[n_]:=Sum[10^j*(Mod[(-1)^j*Floor[(n/2^j + 1)/2],3]), {j,0,Floor[Log2[n]]}]; Array[a, 70, 0] (* Stefano Spezia, Oct 27 2018 *)

a(n) = Sum_{j=0..floor(log_2(n))} 10^j * (floor((n/2^j + 1)/2)*(-1)^j mod 3).

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.

Original entry on oeis.org

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

Henry Bottomley, Apr 04 2001

			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.

Index entries for sequences related to Towers of Hanoi

k appears A001316(k) times in the sequence.

Cf. A001511, A055661, A055662.

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

A060592 Square table by antidiagonals of minimum number of moves between two positions in the 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.

Original entry on oeis.org

0, 1, 1, 1, 0, 1, 3, 1, 1, 3, 3, 3, 0, 3, 3, 2, 3, 2, 2, 3, 2, 3, 2, 2, 0, 2, 2, 3, 2, 2, 1, 1, 1, 1, 2, 2, 3, 1, 3, 1, 0, 1, 3, 1, 3, 7, 2, 2, 1, 1, 1, 1, 2, 2, 7, 6, 6, 3, 2, 2, 0, 2, 2, 3, 6, 6, 7, 5, 7, 2, 3, 2, 2, 3, 2, 7, 5, 7, 6, 6, 6, 6, 3, 3, 0, 3, 3, 6, 6, 6, 6, 7, 5, 7, 5, 5, 3, 1, 1, 3, 5, 5, 7, 5, 7

Offset: 0

Henry Bottomley, Apr 06 2001

			T(4,9)=5 since 4 and 9 written in base 3 are 11 and 100, i.e. the starting position has the first and second disks on peg 1 and the others on peg 0, while the end position has the third disk on peg 1 and the others on peg 0; the five optimal moves between these positions are: move the third disk to peg 2, then the first to peg 2, the second to peg 0, the first to peg 0 and finally the third to peg 1.

Cf. A001511, A007798, A055661, A055662.

A128202 Configuration of discs on pegs after n steps of the optimal solution to the Towers of Hanoi problem moving an odd number of discs from peg 0 to peg 2, or an even number from peg 0 to peg 1.

Original entry on oeis.org

0, 2, 5, 4, 22, 21, 24, 26, 53, 52, 46, 45, 36, 38, 41, 40, 202, 201, 204, 206, 197, 196, 190, 189, 216, 218, 221, 220, 238, 237, 240, 242, 485, 484, 478, 477, 468, 470, 473, 472, 418, 417, 420, 422, 413, 412, 406, 405, 324, 326, 329, 328, 346, 345, 348, 350

Offset: 1

Ralf Stephan, May 09 2007

From Kevin Ryde, Oct 21 2021: (Start)
Configurations are encoded in ternary where the least significant digit is the peg number (0,1,2) which is the location of the smallest disc, the second least significant is the location of the second smallest disc, and so on.
This encoding and these configurations are as in A055661 except that the roles of pegs 1 and 2 are swapped, so ternary digit flip 1<->2, and so a(n) = A004488(A055661(n)).
(End)

Zoran Šunić, Tree morphisms, transducers and integer sequences, arXiv:math/0612080 [math.CO], 2006, see after proposition 5.4.
Index entries for sequences related to Towers of Hanoi

Cf. A007089 (ternary), A004488 (ternary 1<->2).

Cf. A055661 (pegs 1<->2).

a(n) = my(v=binary(bitxor(n,n>>1)),s=(-1)^#v,d=0); for(i=1,#v, if(v[i],d=(d+s)%3,s=-s); v[i]=d); fromdigits(v,3); \\ Kevin Ryde, Oct 21 2021

Name and data corrected and extended by Kevin Ryde, Oct 21 2021

cp's OEIS Frontend

A055662 Successive positions in Tower of Hanoi (with three pegs {0,1,2}) where 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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Views

Author

Keywords

Examples

Links

Crossrefs

A128202 Configuration of discs on pegs after n steps of the optimal solution to the Towers of Hanoi problem moving an odd number of discs from peg 0 to peg 2, or an even number from peg 0 to peg 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions