login
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, 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,3
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, Illustration of row 4
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)
PROG
(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)
CROSSREFS
Cf. A049773.
Sequence in context: A216377 A253515 A319521 * A302436 A283167 A355807
KEYWORD
nonn,tabf
AUTHOR
Rémy Sigrist, Apr 14 2017
STATUS
approved