A281589 - OEIS

%I #38 Jan 26 2022 09:02:27

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

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

%U 26,23,10,15,18,31,2,1,64,33,32,17,48,49,16,9,56,41

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

%C To obtain row n (with n > 0):

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

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

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

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

%C For n > 0:

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

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

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

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

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

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

%H Rémy Sigrist, <a href="/A281589/b281589.txt">Rows n = 1..14, flattened</a>

%H Rémy Sigrist, <a href="/A281589/a281589.jpg">Illustration of row 4</a>

%F From _Jeffrey Shallit_, Sep 04 2021: (Start)

%F a(n) satisfies the recurrences:

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

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

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

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

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

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

%F From _Michel Dekking_, Jan 22 2022: (Start)

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

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

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

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

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

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

%o (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)

%Y Cf. A049773.

%K nonn,tabf

%O 1,3

%A _Rémy Sigrist_, Apr 14 2017