A226893 Number of binary Lyndon words of length n having a conjugate at Hamming distance 2.

0, 1, 2, 3, 6, 9, 14, 20, 26, 40, 42, 72, 62, 123, 102, 208, 114, 405, 146, 668, 290, 1201, 222, 2504, 316, 4356, 800, 8580, 366, 17866, 422, 33312, 2514, 66010, 990, 135960, 614, 262749, 8870, 526256, 762, 1066044, 842

Offset

1,3

Comments

A Lyndon word is an aperiodic word that is lexicographically least in its conjugacy class (of cyclic shifts). A conjugate is a cyclic shift. Hamming distance is the number of positions in which two strings differ.

Links

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

Formula

a(n) = A179674(n) / n. - Falk Hüffner, Aug 15 2021

Example

a(7) = 14, because there are 18 binary Lyndon words of length 7, and all but the following 4 have a conjugate at Hamming distance 2: 0001011, 0001101, 0010111, 0011101.
From Joerg Arndt, Jun 21 2013: (Start)
There are a(8) = 20 Lyndon words of length 8 that have a conjugate at Hamming distance 2 (dots for zeros):
ct:     word      conjugate  word XOR conjugate
01:   1.......    .1......    11......
02:   11......    .11.....    1.1.....
03:   1.1.....    ..1.1...    1...1...
04:   111.....    .111....    1..1....
05:   1..1....    ...1..1.    1.....1.
06:   1111....    .1111...    1...1...
07:   11..1...    1...11..    .1...1..
08:   1.1.1...    ..1.1.1.    1.....1.
09:   1..11...    1...1..1    ...1...1
10:   11111...    .11111..    1....1..
11:   1.1..1..    1..1.1..    ..11....
12:   1.11.1..    1..1.11.    ..1...1.
13:   111.11..    11..111.    ..1...1.
14:   11.111..    11..11.1    ...1...1
15:   111111..    .111111.    1.....1.
16:   111.1.1.    1.111.1.    .1.1....
17:   11.11.1.    .1.11.11    1......1
18:   11111.1.    1.11111.    .1...1..
19:   1111.11.    11.1111.    ..1.1...
20:   1111111.    .1111111    1......1
(End)

Crossrefs

Cf. A001037, A179674.

Sequence in context: A073736 A101593 A349502 * A084628 A325269 A002096

Adjacent sequences: A226890 A226891 A226892 * A226894 A226895 A226896

Keyword

nonn,more

Author

Jeffrey Shallit, Jun 21 2013

Extensions

More terms from Joerg Arndt, Jun 21 2013 and Jun 26 2013

Status

approved