A195467 Consecutive powers of the Gray code permutation.

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

Offset: 0

Author

Tilman Piesk, Sep 23 2011

Keywords

• nonn
• tabf

Comments

The powers of the Gray code permutation (GCP, A003188) form an infinite array, where row n is the n-th power of the GCP. Row 0 is the identity permutation (i.e., the sequence of nonnegative integers), and row 1 is the GCP itself.

The different powers of the n-bit GCP form a matrix of size (A062383(n-1)) X (2^n).

This sequence represents the infinite array in a somewhat redundant way: It shows the rows of all the (2^n) X (2^2^n) matrices of powers of (2^n)-bit GCP. So this sequence forms a triangle, and these 3 matrices are its first 7 rows:

The 1-bit GCP is the identity permutation:

0: 0 1

The 2 different powers of the 2-bit GCP:

0: 0 1 2 3

1: 0 1 3 2

The 4 different powers of the 4-bit GCP:

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

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

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

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

.

This array A can be defined using the binary array B = A197819 by

A = B + 2 * 2stretched(B) + 4 * 4stretched(B) + 8 * 8stretched(B) + ...

where nstretched has the following meaning:

2stretched(1,2,3,4,...) = 1,1,2,2,3,3,4,4,...

4stretched(1,2,3,4,...) = 1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,...

etc.

Links

• Tilman Piesk, First 15 rows of the triangle, flattened
• Tilman Piesk, Explanations (including the 8x256 submatrix) and MATLAB code showing the connection with A197819
• Tilman Piesk, The 8 different powers of the 6-bit Gray code permutation
• Tilman Piesk, Gray code permutation powers (Wikiversity)

Crossrefs

Cf. A003188 (Gray code permutation).

Cf. A006068 (inverse of the Gray code permutation).

Cf. A064706 (square of the Gray code permutation).

Cf. A197819 (this array mod 2).

Extensions

Huge edit by Tilman Piesk, Aug 25 2013