cp's OEIS Frontend

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

This sequence is a variant of A022290; here we consider Fibonacci numbers with negative indices (A039834), there Fibonacci numbers with positive indices (A000045).

After the initial 0, the sequence alternates runs of positive terms and runs of negative terms, the k-th run having 2^(k-1) terms.

The fixed points of T^n are always rational of the form 2k/(2^n+-1) so the number of period n cycles is finite, and h(n) has this form.

A truncated map can be formed T_h(x)=min(h,T(x)) and h(n) is the smallest h for which this map still has a period n cycle (falling between T_0 having only the fixed point 0, and T_1 which is all of T).

This sequence is a permutation of the natural numbers (as odd-indexed terms are not constrained); see A316472 for the inverse sequence.

In the binary plot of the sequence, if the pixel (x, y) is on, then the pixel (2*x, y) is on.

Nodes on a tree with degree k interior nodes and degree 1 boundary nodes.

Sequence generalized: a(n) = a(0)*(B^n) + F(n)* ((B^n)-1)/(B-1); a(0), B integers, F(n) arithmetic function.

Examples:

a(0) = 1, B = 10, F(n) = 1 gives A002275, F(n) = 2 gives A090843, F(n) = 3 gives A097166, F(n) = 4 gives A099914, F(n) = 5 gives A099915.

a(0) = 1, B = 2, F(n) = 1 gives A000225, F(n) = 2 gives A033484, F(n) = 3 gives A036563, F(n) = 4 gives A048487, F(n) = 5 gives A048488, F(n) = 6 gives A048489.

a(0) = 1, B = 3, F(n) = 1 gives A003462, F(n) = 2 gives A048473, F(n) = 3 gives A134931, F(n) = 4 gives A058481, F(n) = 5 gives A116952.

a(0) = 1, B = 4, F(n) = 1 gives A002450, F(n) = 2 gives A020989, F(n) = 3 gives A083420, F(n) = 4 gives A083597, F(n) = 5 gives A083584.

a(0) = 1, B = 5, F(n) = 1 gives A003463, F(n) = 2 gives A057651, F(n) = 3 gives A117617, F(n) = 4 gives A081655.

a(0) = 2, B = 10, F(n) = 1 gives A037559, F(n) = 2 gives A002276.

Start with a node; step one is to connect that node to n+1 new nodes so that it is of degree n+1; further steps are to connect each existing node of degree 1 to n new nodes so that it is of degree n+1; T(n,k) is the total number of nodes after k steps.