login
Consecutive powers of the Gray code permutation.
3

%I #84 Dec 16 2017 23:29:41

%S 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,

%T 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,

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

%N Consecutive powers of the Gray code permutation.

%C 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.

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

%C 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:

%C The 1-bit GCP is the identity permutation:

%C 0: 0 1

%C The 2 different powers of the 2-bit GCP:

%C 0: 0 1 2 3

%C 1: 0 1 3 2

%C The 4 different powers of the 4-bit GCP:

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

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

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

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

%C .

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

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

%C where nstretched has the following meaning:

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

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

%C etc.

%H Tilman Piesk, <a href="/A195467/b195467.txt">First 15 rows of the triangle, flattened</a>

%H Tilman Piesk, <a href="/A195467/a195467_7.txt">Explanations</a> (including the 8x256 submatrix) and <a href="/A195467/a195467_5.txt">MATLAB code</a> showing the connection with A197819

%H Tilman Piesk, <a href="/A195467/a195467_1.txt">The 8 different powers of the 6-bit Gray code permutation</a>

%H Tilman Piesk, <a href="http://en.wikiversity.org/wiki/Gray_code_permutation_powers">Gray code permutation powers</a> (Wikiversity)

%Y Cf. A003188 (Gray code permutation).

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

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

%Y Cf. A197819 (this array mod 2).

%K nonn,tabf

%O 0,5

%A _Tilman Piesk_, Sep 23 2011

%E Huge edit by _Tilman Piesk_, Aug 25 2013