A281589 Triangular array T(n,k), n > 0 and k = 1..2^(n-1), read by rows, in which row n corresponds to the permutation of [1..2^(n-1)] resulting from folding a horizontal strip of paper, with 2^(n-1) square cells numbered from 1 to 2^(n-1), n-1 times.

1, 1, 2, 1, 4, 3, 2, 1, 8, 5, 4, 3, 6, 7, 2, 1, 16, 9, 8, 5, 12, 13, 4, 3, 14, 11, 6, 7, 10, 15, 2, 1, 32, 17, 16, 9, 24, 25, 8, 5, 28, 21, 12, 13, 20, 29, 4, 3, 30, 19, 14, 11, 22, 27, 6, 7, 26, 23, 10, 15, 18, 31, 2, 1, 64, 33, 32, 17, 48, 49, 16, 9, 56, 41

Offset: 1

Author

Rémy Sigrist, Apr 14 2017

Keywords

• nonn
• tabf

Comments

To obtain row n (with n > 0):

- take a strip of paper of dimensions 2^(n-1) X 1

- number the square cells from left to right from 1 to 2^(n-1)

- fold this strip of paper n-1 times, in the middle, covering the left part with the right part; at the end all the cells are stacked on the cell with the number 1

- read the numbers written on square cells from bottom to top.

For n > 0:

- T(n,1) = 1 (the first cell always stays at the bottom)

- T(n+1,2) = 2^n (the last cell covers the first cell after the first folding)

- T(n+1,2^n) = 2 (the second cell comes on top after the last folding).

For n > 0 and k=1..2^(n-2):

- T(n+1,2*k-1) + T(n+1,2*k) = 2^n+1 (opposite cells (summing to 2^n+1) are paired after the first folding).

This sequence has similarities with A049773: here we fold in the middle; there we cut in the middle, covering the left part with the right part.

Links

• Rémy Sigrist, Rows n = 1..14, flattened
• Rémy Sigrist, Illustration of row 4

Crossrefs

Cf. A049773.

Programs

PARI

t(n,k) = my (w=1); my (h=2^(n-1)); my (x=1); my (y=k); while (h>1 && y>1, h /= 2; w *= 2; if (y>h, y = 2*h-y+1; x = w-x+1)); return (x)

Formula

From Jeffrey Shallit, Sep 04 2021: (Start)

a(n) satisfies the recurrences:

a(4n) = a(2n);

a(4n+2) = a(2n) - a(2n+1) + a(4n+1);

a(4n+3) = a(2n+1);

a(8n+1) = -2a(2n+1) + 3*a(4n+1);

a(8n+5) = -a(2n+1) + 2*a(4n+1).

So it is a 2-regular sequence. (End)

From Michel Dekking, Jan 22 2022: (Start)

For n>1 let sigma_n be the uniform morphism of length 2 given by

sigma_n(2j) = 2^n + 1-2j, 2j, for j=1..2^(n-2),

sigma_n(2j+1) = 2j+1, 2^n -2j, for j=0..2^(n-2)-1.

Let T(n,.) be the n-th row of the array T. Then

sigma_n(T(n,.)) = T(n+1,.).

This implies in particular that (a(n)) is a 2-regular sequence. (End)