A217262 Delta sequence for binary words in a minimal-change order (subset-lex Gray code).

0, 1, 2, 1, 0, 3, 0, 1, 2, 1, 0, 1, 4, 1, 0, 1, 2, 1, 0, 3, 0, 1, 2, 1, 0, 1, 2, 5, 2, 1, 0, 1, 2, 1, 0, 3, 0, 1, 2, 1, 0, 1, 4, 1, 0, 1, 2, 1, 0, 3, 0, 1, 2, 1, 0, 1, 2, 3, 6, 3, 2, 1, 0, 1, 2, 1, 0, 3, 0, 1, 2, 1, 0, 1, 4, 1, 0, 1, 2, 1, 0, 3, 0, 1, 2, 1, 0, 1, 2, 5, 2, 1, 0, 1, 2, 1, 0, 3, 0, 1, 2, 1, 0, 1, 4, 1, 0, 1, 2, 1, 0, 3, 0, 1, 2, 1, 0, 1, 2, 3, 4

Offset: 0

Author

Joerg Arndt, Sep 29 2012

Keywords

• nonn

Comments

Positions of change with a certain Gray code (SL-Gray) for binary words (see example): to keep the sequence independent of the word length we start with the all-ones word, the sequence gives the following changes. The Gray code is cyclic, so first words skipped can (for fixed word length) be appended to the end.

Alternatively, for words length n, start with the all-zeros word, use transitions (n-2), (n-1), (n-2), (n-3), (n-4), ..., 3, 2, 1, 0, followed by the terms of this sequence until all 2^n words have been visited (see rows 00..05 in the example).

The subset-lex Gray code shown here can be obtained by a reflection process from the (reversed) subset-lexicographic order for binary words given in A108918.

Research problem: Does a two-close Gray code exist for the binary words of length n for all n? One-close Gray codes for binary words exists for n<=6 but not for n=7 (and unlikely for any n>=8, see Fxtbook link).

From Joerg Arndt, Apr 29 2014: (Start)

Sequence can be obtained from A007814 by replacing 0 by 01210, 1 by 3, 2 by 141, 3 by 12521, 4 by 1236321, ..., n by 123..(n-1)(n+2)(n-1)..321. - Joerg Arndt, Apr 29 2014

The consecutive transitions are either one-close (abs(a(n)-a(n-1))=1, most of the time) or 3-close (abs(a(n)-a(n-1))=3): In the Gray code of the 2^n n-bit words all transitions are one-close but for 2^(n-2) - 2 transitions that are 3-close; The Gray codes for n<=3 have only one-close transitions.

(End)

The positions of 0's are twice the terms of A327492. - Andrey Zabolotskiy, Jan 06 2024

Examples

			Example for word length 5:
no:    word     transition
00:    .....    .1...  3
01:    1....    1....  4
02:    11...    .1...  3
03:    111..    ..1..  2
04:    1111.    ...1.  1
05:    11111    ....1  0 <--= sequence starts
06:    111.1    ...1.  1
07:    11..1    ..1..  2
08:    11.11    ...1.  1
09:    11.1.    ....1  0
10:    1..1.    .1...  3
11:    1..11    ....1  0
12:    1...1    ...1.  1
13:    1.1.1    ..1..  2
14:    1.111    ...1.  1
15:    1.11.    ....1  0
16:    1.1..    ...1.  1
17:    ..1..    1....  4
18:    ..11.    ...1.  1
19:    ..111    ....1  0
20:    ..1.1    ...1.  1
21:    ....1    ..1..  2
22:    ...11    ...1.  1
23:    ...1.    ....1  0
24:    .1.1.    .1...  3
25:    .1.11    ....1  0
26:    .1..1    ...1.  1
27:    .11.1    ..1..  2
28:    .1111    ...1.  1
29:    .111.    ....1  0
30:    .11..    ...1.  1
31:    .1...    ..1..  2
Append first few words to obtain Gray code for word length 5:
00:    .....    .1...
01:    1....    1....
02:    11...    .1...
03:    111..    ..1..
04:    1111.    ...1.
		

Links

• Joerg Arndt, Table of n, a(n) for n = 0..4095
• Joerg Arndt, Matters Computational (The Fxtbook), section 20.3.2 "Adjacent changes (AC) Gray codes", p.400.
• Joerg Arndt, C++ code to compute this sequence.
• Joerg Arndt, Subset-lex: did we miss an order?, arXiv:1405.6503 [math.CO], (26-May-2014)

Crossrefs

Cf. A007814 (transitions for the binary reflected Gray code).

Cf. A108918.

Extensions

Prepended a(0)=0, Joerg Arndt, Apr 29 2014