cp's OEIS Frontend

Let S be the set of numbers defined by these rules: 1 is in S, and if x is in S, then x+1 and 1/x are in S. Then S is the set of positive rational numbers, which arise in generations as follows: g(1) = (1/1), g(2) = (1+1) = (2), g(3) = (2+1, 1/2) = (3/1, 1/2), g(4) = (4/1, 1/3, 3/2), ... . Once g(n-1) = (g(1), ..., g(z)) is defined, g(n) is formed from the vector (g(1) + 1, 1/g(1), g(2) + 1, 1/g(2), ..., g(z) + 1, 1/g(z)) by deleting all elements that are in a previous generation. A226080 is the sequence of denominators formed by concatenating the generations g(1), g(2), g(3), ... . It is easy to prove the following:

(1) Every positive rational is in S.

(2) The number of terms in g(n) is the n-th Fibonacci number, F(n) = A000045(n).

(3) For n > 2, g(n) consists of F(n-2) numbers < 1 and F(n-1) numbers > 1, hence the name "rabbit ordering" since the n-th generation has F(n-2) reproducing pairs and F(n-1) non-reproducing pairs, as in the classical rabbit-reproduction introduction to Fibonacci numbers.

(4) The positions of integers in S are the Fibonacci numbers.

(5) The positions of 1/2, 3/2, 5/2, ..., are Lucas numbers (A000032).

(6) Continuing from (4) and (5), suppose that n > 0 and 0 < r < n, where gcd(n,r) = 1. The positions in A226080 of the numbers congruent to r mod n comprise a row of the Wythoff array, W = A035513. The correspondence is sampled here:

row 1 of W: positions of n+1 for n>=0,

row 2 of W: positions of n+1/2,

row 3 of W: positions of n+1/3,

row 4 of W: positions of n+1/4,

row 5 of W: positions of n+2/3,

row 6 of W: positions of n+1/5,

row 7 of W: positions of n+3/4.

(7) If the numbers <=1 in S are replaced by 1 and those >1 by 0, the resulting sequence is the infinite Fibonacci word A003849 (except for the 0-offset first term).

(8) The numbers <=1 in S occupy positions -1 + A001950, where A001950 is the upper Wythoff sequence; those > 1 occupy positions given by -1 + A000201, where A000201 is the lower Wythoff sequence.

(9) The rules (1 is in S, and if x is in S, then 1/x and 1/(x+1) are in S) also generate all the positive rationals.

A variant which extends this idea to an ordering of all rationals is described in A226130. - M. F. Hasler, Jun 03 2013

The updown and downup zigzag limits are (-1 + sqrt(5))/2 and (1 + sqrt(5))/2; see A020651. - Clark Kimberling, Nov 10 2013

From Clark Kimberling, Jun 19 2014: (Start)

Following is a guide to related trees and sequences; for example, the tree A226080 is represented by (1, x+1, 1/x), meaning that 1 is in S, and if x is in S, then x+1 and 1/x are in S (except for x = 0).

All the positive integers:

A243571, A243572, A232559 (1, x+1, 2x)

A232561, A242365, A243572 (1, x+1, 3x)

A243573 (1, x+1, 4x)

All the integers:

A243610 (1, 2x, 1-x)

A232723, A242364

All the positive rationals:

A226080, A226081, A242359, A242360 (1, x+1, 1/x)

A243848, A243849, A243850 (1, x+1, 2/x)

A243851, A243852, A243853 (1, x+1, 3/x)

A243854, A243855, A243856 (1, x+1, 4/x)

A243574, A242308 (1, 1/x, 1/(x+1))

A241837, A243575 ({1,2,3}, x+4, 12/x)

A242361, A242363 (1, 1 + 1/x, 1/x)

A243613, A243614 (0, x+1, x/(x+1))

All the rationals:

A243611, A243612 (0, x+1, -1/(x+1))

A226130, A226131 (1, x+1, -1/x)

A243712, A243713 ({1,2,3}, x+1, 1/(x+1))

A243730, A243731 ({1,2,3,4}, x+1, 1/(x+1))

A243732, A243733 ({1,2,3,4,5}, x+1, 1/(x+1))

A243714, A243715

A243925, A243926, A243927 (1, x+1, -2/x)

A243928, A243929, A243930 (1, x+1, -3/x)

All the Gaussian integers:

A243924 (1, x+1, i*x)

All the Gaussian rational numbers:

A233694, A233695, A233696 (1, x+1, i*x, 1/x).

(End)

Let S be the set of numbers defined by these rules: 1 is in S, and if x is in S, then x + 1 and 2*x are in S. Then S is the set of all positive integers, which arise in generations. Deleting duplicates as they occur, the generations are given by g(1) = (1), g(2) = (2), g(3) = (3,4), g(4) = (6,5,8), g(5) = (7,12,10,9,16), etc. Concatenating these gives A232559, a permutation of the positive integers. The number of numbers in g(n) is A000045(n), the n-th Fibonacci number. It is helpful to show the results as a tree with the terms of S as nodes and edges from x to x + 1 if x + 1 has not already occurred, and an edge from x to 2*x if 2*x has not already occurred. The positions of the odd numbers are given by A026352, and of the evens, by A026351.

The previously mentioned tree is an example of a fractal tree; that is, an infinite rooted tree T such that every complete subtree of T contains a subtree isomorphic to T. - Clark Kimberling, Jun 11 2016

The similar sequence S', generated by these rules: 0 is in S', and if x is in S', then 2*x and x+1 are in S', and duplicates are deleted as they occur, appears to equal A048679. - Rémy Sigrist, Aug 05 2017

From Katherine E. Stange and Glen Whitney, Oct 09 2021: (Start)

The beginning of this tree is

1

|

2

/ \

3..../ \......4

| / \

6 5.../ \...8

/ \ | / \

7/ \12 10 9/ \16

This tree contains every positive integer, and one can show that the path from 1 to the integer n is exactly the sequence of intermediate values observed during the Double-And-Add Algorithm AKA Chandra Sutra Method (namely, the algorithm which begins with m = 0, reads the binary representation of n from left to right, and, for each digit 0 read, doubles m, and for each digit 1 read, doubles m and then adds 1 to m; when the algorithm terminates, m = n).

As such, the path between 1 and n is a function of the binary expansion of n. The elements of the k-th row of the tree (generation g(k)) are all those elements whose binary expansion has k_1 digits and Hamming weight k_2, for some k_1 and k_2 such that k_1 + k_2 = k + 1.

The depth at which integer n appears in this tree is given by A014701(n) = A056792(n)-1. For example, the depth of 1 is 0, the depth of 2 is 1, and the depths of 3 and 4 are both 2. (End)

Definition need not invoke deletion: Tree is rooted at 1, all even nodes have x+1 as a child, all nodes have 2*x as a child, and any x+1 child precedes its sibling. - Robert Munafo, May 08 2024

Decree that (row 1) = (1), (row 2) = (2), and (row 3) = (3). For n >= 4, row n consists of numbers in decreasing order generated as follows: x+1 for each x in row n-1 together with 2/x for each x in row n-1, and duplicates are rejected as they occur. Every positive rational number occurs exactly once in the resulting array. Let c(n) be the number of numbers in (row n); it appears that (c(n)) is not linearly recurrent.

Decree that row 1 is (1), row 2 is (2, 3), and row 3 is (4, 6, 9). Let r(n) = A001590(n+2), so that r(r) = r(n-1) + r(n-2) + r(n-3) with r(1) =1, r(2) = 2, r(3) = 3. Row n of the array, for n >= 4, consists of the numbers, in increasing order, defined as follows: all 3*x from x in row n-1, together with all 1 + 3*x from x in row n-2, together with all 2 + 3*x from x in row n-3. Thus, the number of numbers in row n is r(n), a tribonacci number. Every positive integer occurs exactly once in the array, so that the resulting sequence is a permutation of the positive integers.

Decree that (row 1) = (1), (row 2) = (2, 4), (row 3) = (3,5,8,16), (row 4) = (6,9,12,17,20,32,64). Let r(n) = A001563(n+3), so that r(r) = r(n-1) + r(n-2) + r(n-3) + r(n-4) with r(1) =1, r(2) = 2, r(3) = 4, r(4) = 7. Row n of the array, for n >= 5, consists of the numbers, in increasing order, defined as follows: all 4*x from x in row n-1, together with all 1 + 4*x from x in row n-2, together with all 2 + 4*x from x in row n-3, together with all 3 + 4*x for x in row n-4. Thus, the number of numbers in row n is r(n), a tetranacci number. Every positive integer occurs exactly once in the array, so that the resulting sequence is a permutation of the positive integers.

Decree that (row 1) = (1), (row 2) = (2), and (row 3) = (3). For n >= 4, row n consists of numbers in decreasing order generated as follows: x+1 for each x in row n-1 together with 2/x for each x in row n-1, and duplicates are rejected as they occur. Every positive rational number occurs exactly once in the resulting array. Let c(n) be the number of numbers in (row n); it appears that (c(n)) is not linearly recurrent.

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

Let F = A000045 (the Fibonacci numbers). To construct the array, decree the first 4 rows as in the Example. Thereafter, row n consists of F(n) numbers in increasing order, generated as follows: the F(n-1) numbers 2*x from x in row n-1, together with the F(n-2) numbers 1 - 2*x from numbers x in row n-2. For n >= 3, row n consists of F(n-1) negative integers and F(n-2) positive integers; also, row n consists of F(n-1) even integers and F(n-2) odd integers. Conjecture: Every row contains F(k) or -F(k) for some k.

Theorem: S_n contains Fibonacci(n+2) elements.

Proof from Adam P. Goucher, Jan 12 2022 (Start)

Let 'D' and 'I' be the 'double' and 'increment' operators, acting on 0 from the right. Then every element of S_n can be written as a length-n word over {D,I}. E.g., S_4 contains

0: DDDD

1: DDDI

2: DDID

3: DIDI

4: DIDD

5: IDDI

6: IDID

8: IDDD

We can avoid having two adjacent 'I's (because we can transform it into an equivalent word by prepending a 'D' -- which has no effect -- and then replacing the first 'DII' with 'ID').

Subject to the constraint that there are no two adjacent 'I's, these 'II'-less words all represent distinct integers (because of the uniqueness of binary expansions).

So we're left with the problem of enumerating length-n words over the alphabet {I, D} which do not contain 'II' as a substring. These are easily seen to be the Fibonacci numbers because we can check n=0 and n=1 and verify that the recurrence relation holds since a length-n word is either a length-(n-1) word followed by 'D' or a length-(n-2) word followed by 'DI'. QED (End)

From Rémy Sigrist, Jan 12 2022: (Start)

For any m >= 0, the value m first appears on row A056792(m).

For any n > 0: row n minus row n-1 corresponds to row n of A243571.

(End)