cp's OEIS Frontend

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.

%I A281589 #38 Jan 26 2022 09:02:27
%S A281589 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 A281589 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 A281589 26,23,10,15,18,31,2,1,64,33,32,17,48,49,16,9,56,41
%N 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.
%C A281589 To obtain row n (with n > 0):
%C A281589 - take a strip of paper of dimensions 2^(n-1) X 1
%C A281589 - number the square cells from left to right from 1 to 2^(n-1)
%C A281589 - 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 A281589 - read the numbers written on square cells from bottom to top.
%C A281589 For n > 0:
%C A281589 - T(n,1) = 1 (the first cell always stays at the bottom)
%C A281589 - T(n+1,2) = 2^n (the last cell covers the first cell after the first folding)
%C A281589 - T(n+1,2^n) = 2 (the second cell comes on top after the last folding).
%C A281589 For n > 0 and k=1..2^(n-2):
%C A281589 - 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 A281589 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 A281589 Rémy Sigrist, <a href="/A281589/b281589.txt">Rows n = 1..14, flattened</a>
%H A281589 Rémy Sigrist, <a href="/A281589/a281589.jpg">Illustration of row 4</a>
%F A281589 From _Jeffrey Shallit_, Sep 04 2021: (Start)
%F A281589 a(n) satisfies the recurrences:
%F A281589 a(4n) = a(2n);
%F A281589 a(4n+2) = a(2n) - a(2n+1) + a(4n+1);
%F A281589 a(4n+3) = a(2n+1);
%F A281589 a(8n+1) = -2a(2n+1) + 3*a(4n+1);
%F A281589 a(8n+5) = -a(2n+1) + 2*a(4n+1).
%F A281589 So it is a 2-regular sequence.  (End)
%F A281589 From _Michel Dekking_, Jan 22 2022: (Start)
%F A281589 For n>1 let sigma_n be the uniform morphism of length 2 given by
%F A281589     sigma_n(2j) = 2^n + 1-2j, 2j, for j=1..2^(n-2),
%F A281589     sigma_n(2j+1) = 2j+1, 2^n -2j, for j=0..2^(n-2)-1.
%F A281589 Let T(n,.) be the n-th row of the array T. Then
%F A281589     sigma_n(T(n,.)) = T(n+1,.).
%F A281589 This implies in particular that (a(n)) is a 2-regular sequence. (End)
%o A281589 (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 A281589 Cf. A049773.
%K A281589 nonn,tabf
%O A281589 1,3
%A A281589 _Rémy Sigrist_, Apr 14 2017