login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A239303 Triangle of compressed square roots of Gray code * bit-reversal permutation. 2
1, 3, 1, 6, 1, 5, 6, 9, 1, 10, 12, 18, 1, 17, 10, 12, 18, 33, 1, 34, 20, 24, 36, 66, 1, 65, 34, 20, 24, 36, 66, 129, 1, 130, 68, 40, 48, 72, 132, 258, 1, 257, 130, 68, 40, 48, 72, 132, 258, 513, 1, 514, 260, 136, 80 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

The permutation that turns a natural ordered into a sequency ordered Walsh matrix of size 2^n is the product of the Gray code permutation A003188(0..2^n-1) and the bit-reversal permutation A030109(n,0..2^n-1).

(This permutation of 2^n elements can be represented by the compression vector [2^(n-1), 3*[2^(n-2)..4,2,1]] with n elements.)

This triangle shows the compression vectors of the unique square roots of these permutations, which correspond to symmetric binary matrices with 2n-1 ones.

(These n X n matrices correspond to graphs that can be described by permutations of n elements, which are shown in A239304.)

Rows of the square array:

T(1,n) = 1,3,6,6,12,12,24,24,48,48,96,96,192,192,384,384,... (compare A003945)

T(2,n) = 1,1,9,18,18,36,36,72,72,144,144,288,288,576,576,... (compare A005010)

Columns of the square array:

T(m,1) = 1,1,5,10,10,20,20,40,40,80,80,160,160,320,320,... (compare A146523)

T(m,2) = 3,1,1,17,34,34,68,68,136,136,272,272,544,544,... (compare A110287)

LINKS

Tilman Piesk, First 140 rows of the triangle, flattened

Tilman Piesk, Sequency ordered Walsh matrix (Wikiversity)

Tilman Piesk, Calculation in MATLAB

EXAMPLE

Triangular array begins:

   1

   3   1

   6   1   5

   6   9   1  10

  12  18   1  17  10

  12  18  33   1  34  20

Square array begins:

   1   3   6   6  12  12

   1   1   9  18  18  36

   5   1   1  33  66  66

  10  17   1   1 129 258

  10  34  65   1   1 513

  20  34 130 257   1   1

The Walsh permutation wp(8,12,6,3) = (0,8,12,4, 6,14,10,2, 3,11,15,7, 5,13,9,1) permutes the natural ordered into the sequency ordered Walsh matrix of size 2^4.

Its square root is wp(6,9,1,10) = (0,6,9,15, 1,7,8,14, 10,12,3,5, 11,13,2,4).

So row 4 of the triangular array is (6,9,1,10).

CROSSREFS

Cf. A239304, A003188, A030109.

Sequence in context: A169814 A068436 A019570 * A040011 A066446 A069625

Adjacent sequences:  A239300 A239301 A239302 * A239304 A239305 A239306

KEYWORD

nonn,tabl

AUTHOR

Tilman Piesk, Mar 14 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 20 19:27 EDT 2021. Contains 343137 sequences. (Running on oeis4.)