cp's OEIS Frontend

As a sequence, {a(n)} permutes the positive integers. As an array, {T(n,k)} is an interspersion-dispersion or I-D array (refer to Kimberling, 1st linked reference).

The top row of {T(n,k)} is A000079 or powers of two = 1, 2, 4, 8, 16, ....

Except for the leftmost element "1" of the top row, rows of T(n,k) indexed n = 0, 1, 2, ..., consist entirely of even numbers (A005843) for n even and entirely of odd numbers (A005408) for n odd.

The left column (k = 1) of {T(n,k)} comprises a "1" for the top row (n = 0) and A004755(n) = n + 2^(floor(log_2(n)) + 1), for rows n = 1, 2, 3, ....

For rows indexed n = 0, 1, 2, ..., and columns indexed k = 1, 2, 3, ..., T(n,k) is given by T(0,k) = L^(k - 1)(1) and T(n,k) = L^(k - 1) R(n) for n = 1, 2, 3, ..., the image of n under a composition of branching functions L(n) = A004754(n) = n + 2^floor(log_2(n)) and R(n) = A004755(n) = n + 2^(floor(log_2(n)) + 1) (cf. generating tree A059893 and 2nd linked reference).

(Duality with array A054582): Consider A059893 and A000027 as labeled binary trees arranging the positive integers. In latter tree, node labels equal node positions, thus following their natural order. Rows of {T(n,k)} are the labels along maximal straight paths that always branch left in the former tree, while rows of (transposed) array A054582 are the labels along maximal straight paths that always branch left in the latter tree.

Column k of {T(n,k)} comprises the (sorted) labels in the k-th right clade of latter tree, while column k of (transposed) A054582 comprises the (sorted) labels in the k-th right clade of the former tree. This makes the arrays {T(n,k)} and (transposed) A054582 "blade-duals," blade being a contraction of branch-clade ('right clades' explained under tree A345253 and in 2nd link).

Write the positive integers in natural order as a (left-justified) "tetrangle" or "irregular triangle" tableau with 2^t entries on each row t, for t=1, 2, 3, .... Then, columns of the tableau equal rows of {T(n,k)} (2nd link):

1,

2, 3,

4, 5, 6, 7,

8, 9, 10, 11, 12, 13, 14, 15

16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,

...

Analogous to A345252, its right-justified tableau of the positive integers in cohorts with lengths the Fibonacci numbers replaced by the above left-justified tableau with powers of two as lengths of the cohorts.

(Mirror duality): A "mirror dual" I-D array or "inverse I-D array" (see Kimberling, 1st linked reference) is obtained by substituting the left-justified tableau by a right-justified tableau and following the identical procedure, or equivalently by mirroring the tree A059893 cited above, i.e., taking maximal straight paths that always branch right in the tree A059893. With two types of duality then, {T(n,k)} forms a quartet of I-D arrays together with its mirror dual, its blade dual (transposed) A054582 and mirror dual A191448 of the latter.

(Para-sequences): Sequences of row and column indices (see Conway-Sloane correspondence under A019586, citing Kimberling). For rows indexed n = 0, 1, 2, ..., and columns indexed k = 1, 2, 3, ..., the row index n of positive integer T(n,k) is A053645(T) and the column index k of positive integer T(n,k) is A065120(T).

Every positive integer occurs exactly once, so that, as a sequence, a(n) is a permutation of the positive integers.

Descending from the root node 1, generate tree by outer composition of L(n) = n + F(Finv(n)) and R(n) = n + F(Finv(n) + 1), respectively, according to left or right branching, where F(n) = A000045(n) are the Fibonacci numbers and Finv(n) = A130233(n) is the 'lower' Fibonacci inverse. This produces each number by maximal Fibonacci expansion (cf. example below of Method 2, entry A343152, and links).

(Level of tree): The number of terms in this expansion of n is the level of the tree on which n appears, A112310(n-1) + 1 = A200648(n+1). The number of terms in the expansion of a(n) is floor(log_2(n)) + 1 = A113473(n) = A070939(n) = A029837(n+1).

"Maximal Fibonacci expansion" maximizes the sum of coefficients over all Fibonacci numbers (of positive index), allowing both F(1) = 1 and F(2) = 1. Thus, it is just an expansion and not a representation (like "greedy" and "lazy"), as it "breaks the rule" by using two bits that correspond to elements of equal value, rather than using distinct basis elements (link). This reveals connections to the cf. sequences: Binary strings that emerge in lexicographic order from "maximal Fibonacci gaps" (example), binary trees of the positive integers, and I-D arrays "harvested" from the trees. To define the expansion uniquely, always include F(1), so that the expansion of positive integer n equals F(1) for n = 1 and F(1) prepended to the lazy Fibonacci representation of n-1 for n > 1. Hence, a(1) = 1, and for n > 1, a(n) = A095903(n-1) + 1. The "redundant" expansion arranges the positive integers in the single binary tree {T(n,k)}, rather than the two trees at A255773 and A255774 that result from representation (see link).

(Left-to-right order in tree): Each F(t)-sized block (F(t+1), ..., F(t+2) - 1) of successive positive integers ("Fibonacci cohort" t) appears in right-to-left order in the tree as reordered in A343152, where elements of each cohort appear consecutively (see link).

Descending from the root node 1, generate tree by the inner composition of A026351 and A026352, that is, one plus the sequences of lower and upper Wythoff numbers, A000201 and A001950, respectively, according to left or right branching (see example below of Method 1 and links).

Generate tree from (one plus) the number of (initial) zeros on the positive integers for the outer composition of sequences, A060143 and A060144, respectively, according to left or right branching descending from the identity (c.f example below of Method 3 and links).

The lower Wythoff numbers, A000201, appear exclusively in the 1st, 3rd, 5th, ... right clades of the tree, while the upper Wythoff numbers A001950, appear exclusively in the 2nd, 4th, 6th, ... right clades of the tree. Here, the k-th right clade comprises the nodes at positions 2^(k+1) and 2^k + 1, together with all descendants of the latter (link).

(Duality with tree A232560, and related arrays): Consider the labeled binary trees a(n) = A232560(A059893(n)) and A232560(n) = a(A059893(n)). Labels along maximal straight paths that always branch left in a(n) give rows of array A345252, while labels along maximal straight paths that always branch left in A232560 give rows of array A083047.

Sorting the labels from each successive right clade of the binary tree a(n) gives the successive columns of A083047, while sorting labels from each successive right clade of A232560 gives each successive column of A345252. This makes the trees a(n) and A232560 "blade-duals," blade being a contraction of branch-clade (see entry for A345254 and link). A200648(n)+1 gives the level of the tree on which elements of array first-columns A345252(n,1) and A083047(n,1) appear.

(Palindromes and coincidence of elements): Trees a(n) and A232560 coincide when the sequence of left and right branching is a palindrome: a(A329395(n)) = A232560(A329395(n)). As Kimberling notes (cf. A059893), this happens at fixed points of A059893(n) or, equivalently, at n for which A081242(n) is a palindrome.

The inverse permutation of a(n) as a sequence can be read from a "tetrangle" or "irregular triangle" tableau with F(t) (Fibonacci number) entries on each row t, for t = 1, 2, 3, ..., in which an entry on row t is 2*x the entry x immediately above it on row t-1, if such exists, or otherwise 2*x + 1 the entry x in the corresponding position on row t-2 (thus generating new rows as in A243571 but without sorting the numbers into increasing order, linked reference):

1,

2,

3, 4,

5, 6, 8,

7, 9, 10, 12, 16,

11, 13, 17, 14, 18, 20, 24, 32,

...

With the right-justified tableau substituted by a left-justified tableau, the same procedure yields the inverse permutation for the "minimal Fibonacci tree," A048680(A059893(n)), the "cohort-dual" tree of a(n), where "cohort" t is the F(t)-sized block of successive entries in the tableau (see entry for A345252, linked reference).

(Coincidence of elements): a(A020988(n)) = A048680(A059893(A020988(n))) = A099919(n) and a(A020989(n)) = A048680(A059893(A020989(n))) = A049651(n). Collectively, a(A061547(n)) = A048680(A059893(A061547(n))) = union(A049651(n), A099919(n)).

With two types of duality, the tree forms a quartet of binary-tree arrangements of the positive integers, together with its blade dual A232560, its cohort dual A048680(A059893), and blade dual A048680 of the latter.

Order in the tree is "memory-less": Let a(n) and a(m) label nodes at positions n and m, respectively. Let d1 and d2 be two descending paths, i.e., sequences branching left or right from a starting node. (Nodal positions for the left and right children of the node at position p are given by 2*p and 2*p + 1, resp., and d1 and d2 are compositions of these.) Then a(d1(n)) < a(d2(n)) if and only if a(d1(m)) < a(d2(m)) (linked reference).

As a sequence, {a(n)} permutes the positive integers. As an array, {T(n,k)} is an interspersion-dispersion or I-D array (refer to Kimberling, 1st linked reference).

The top row of {T(n,k)} is A000071 or one less than the Fibonacci numbers = 1, 2, 4, 7, 12, ....

The top row of {T(n,k)} alternates lower and upper Wythoff numbers, A000201 and A001950, respectively, while all subsequent rows consist entirely of lower Wythoff numbers or entirely of upper Wythoff numbers (cf. generating tree A345253).

The left column (k = 1) of {T(n,k)} is n + F(Finv(n) + 1), for rows indexed n = 0, 1, 2, ..., where F(n) = A000045(n) are the Fibonacci numbers and Finv(n) = A130233(n) is the 'lower' Fibonacci inverse.

For rows indexed n = 0, 1, 2, ..., and columns indexed k = 1, 2, 3, ..., T(n,k) is given by T(n,k) = L^(k - 1) R(n), the image of n under a composition of branching functions L(n) = n + F(Finv(n)) and R(n) = n + F(Finv(n) + 1) (cf. generating tree A345253).

Write the positive integers in natural order (A000027) as a right-justified "tetrangle" or "irregular triangle" tableau with F(t) (Fibonacci number) entries on each row t, for t = 1, 2, 3, .... Then, columns of the tableau equal rows of {T(n,k)} (2nd linked reference):

1,

2,

3, 4,

5, 6, 7,

8, 9, 10, 11, 12,

13, 14, 15, 16, 17, 18, 19, 20,

...

(Duality with array A194030): With the right-justified tableau substituted by a left-justified tableau, the above procedure yields the array A194030, making {T(n,k)} and A194030 "cohort-dual" arrays, where "cohort" t is the F(t)-sized block (F(t + 1), ..., F(t + 2) - 1) of successive positive integers on row t of both tableaux (2nd link under references, which calls A194030 the "1-2-Fibonacci cohort array", by analogy).

Analogous to A345254, its left-justified tableau of the positive integers in cohorts with lengths powers of two replaced by the above right-justified tableau with the Fibonacci numbers as lengths of the cohorts.

(Duality with array A083047): Consider the labeled binary trees A345253(n) = A232560(A059893(n)) and A232560(n) = A345253(A059893(n)). Rows of array {T(n,k)} are the labels along maximal straight paths that always branch left in A345253, while rows of array A083047 are the labels along maximal straight paths that always branch left in A232560.

Column k of {T(n,k)} comprises the (sorted) labels in the k-th right clade of binary tree A232560, while column k of A083047 comprises the (sorted) labels in the k-th right clades of binary tree A345253. This makes the arrays {T(n,k)} and A083047 "blade-duals", blade being a contraction of branch-clade (cf. A345253 and 2nd linked reference).

(Mirror duality): A "mirror dual" I-D array or "inverse I-D array" (see Kimberling in 1st linked reference) is obtained by mirroring the tree A345253 cited above, i.e., taking maximal straight paths that always branch right in A345253. With three types of duality then, {T(n,k)} forms an octet of I-D arrays together with its cohort dual A194030 and mirror duals of these two, its blade dual A083047 and cohort dual A035513 of the latter, and their respective mirror duals, A132817 and A191436.

(Para-sequences): Sequences of row and column indices (see Conway-Sloane correspondence under A019586, citing Kimberling). For rows indexed n = 0, 1, 2, ..., the row index n of positive integer T(n,k) follows a right-justified tableau with F(t) entries on each row t, for t = 1, 2, 3, ..., in which an entry on row t equals the entry immediately above it on row t-1, if such exists, or otherwise equals the minimum positive integer excluded from the tableau so far:

0,

0,

1, 0,

2, 1, 0,

3, 4, 2, 1, 0,

5, 6, 7, 3, 4, 2, 1, 0,

...

For columns indexed k = 1, 2, 3, ..., the column index k of positive integer T(n,k) follows a right-justified tableau with F(t) entries on each row t, for t = 1, 2, 3, ..., in which an entry x+1 on row t equals one plus the entry x immediately above it on row t-1, if such exists, or otherwise equals one:

1,

2,

1, 3,

1, 2, 4,

1, 1, 2, 3, 5,

1, 1, 1, 2, 2, 3, 4, 6,

...

A self-inverse permutation of the natural numbers.

Analogous to A059893 with binary expansion replaced by maximal Fibonacci expansion.

Analogous to A343150 with minimal Fibonacci expansion replaced by maximal Fibonacci expansion.

For n=1, the expansion equals 1. For n>=2, the expansion equals A104326(n-1) with a 1 appended. The 1 corresponds to a digit (always equal to 1) for F(1)=1, in addition to the digit for F(2)=1. (This expansion is NOT a representation, see reference in link, pp. 106 and 137.)

Write the sequence as a (right-justified) "tetrangle" or "irregular triangle" tableau with F(t) (Fibonacci number) entries on each row, for t=1,2,3,.... Then, columns of the tableau equal rows of the array A083047 (see reference in link, p. 131):

1

2

3, 4

6, 5, 7

8, 11, 10, 9, 12

16, 14, 19, 13, 18, 17, 15, 20

...

A self-inverse permutation of the natural numbers.

Analogous to A059893 with binary expansion replaced by minimal Fibonacci expansion.

Analogous to A343152 with maximal Fibonacci expansion replaced by minimal Fibonacci expansion.

The expansion of n equals A014417(n) with a 0 appended (see reference in link, p. 144).

Write the sequence as a (left-justified) "tetrangle" or "irregular triangle" tableau with F(t) (Fibonacci number) entries on each row, for t=1,2,3,.... Then, columns of the tableau equal rows of the Wythoff array, A035513 (see reference in link, p. 131):

1

2

3, 4

5, 7, 6

8, 11, 10, 9, 12

13, 18, 16, 15, 20, 14, 19, 17

...

Any of these integers can be expressed by a composition of floor functions f(n) = [mu*n] and g(n) = [nu*n], provided that the composition applies at least one f(n) and one g(n), for an irrational slope 1 < mu < 2 and its conjugate nu = 1/(1-1/mu). This follows from the Rayleigh-Beatty theorem. See reference in link. A064801 gives "floor squares."