A232561 -id:A232561 - cp's OEIS frontend

A226080 Denominators in the Fibonacci (or rabbit) ordering of the positive rational numbers.

1, 1, 1, 2, 1, 3, 2, 1, 4, 3, 2, 3, 1, 5, 4, 3, 4, 2, 5, 3, 1, 6, 5, 4, 5, 3, 7, 4, 2, 7, 5, 3, 5, 1, 7, 6, 5, 6, 4, 9, 5, 3, 10, 7, 4, 7, 2, 9, 7, 5, 7, 3, 8, 5, 1, 8, 7, 6, 7, 5, 11, 6, 4, 13, 9, 5, 9, 3, 13, 10, 7, 10, 4, 11, 7, 2, 11, 9, 7, 9, 5, 12, 7

Offset: 1

Clark Kimberling, May 25 2013

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)

			The denominators are read from the rationals listed in "rabbit order":
1/1, 2/1, 3/1, 1/2, 4/1, 1/3, 3/2, 5/1, 1/4, 4/3, 5/2, 2/3, 6/1, ...

Clark Kimberling, Table of n, a(n) for n = 1..6000
Clark Kimberling, The infinite Fibonacci tree and other trees generated by rules, Proceedings of the 16th International Conference on Fibonacci Numbers and Their Applications, Fibonacci Quarterly 52 (2014), no. 5, pp. 136-149.
Index entries for fraction trees

Cf. A000045, A035513, A226081 (numerators), A226130, A226247, A020651.

z = 10; g[1] = {1}; g[2] = {2}; g[3] = {3, 1/2};
j[3] = Join[g[1], g[2], g[3]]; j[n_] := Join[j[n - 1], g[n]];
d[s_List, t_List] := Part[s, Sort[Flatten[Map[Position[s, #] &, Complement[s, t]]]]]; j[3] = Join[g[1], g[2], g[3]]; n = 3; While[n <= z, n++; g[n] = d[Riffle[g[n - 1] + 1, 1/g[n - 1]], g[n - 2]]];
Table[g[n], {n, 1, z}]; j[z] (* rabbit-ordered rationals *)
Denominator[j[z]]  (* A226080 *)
Numerator[j[z]]    (* A226081 *)
Flatten[NestList[(# /. x_ /; x > 1 -> Sequence[x, 1/x - 1]) + 1 &, {1}, 9]] (* rabbit-ordered rationals, Danny Marmer, Dec 07 2014 *)

A226080_vec(N=100)={my(T=[1],S=T,A=T); while(N>#A=concat(A, apply(denominator, T=select(t->!setsearch(S,t), concat(apply(t->[t+1,1/t],T))))), S=setunion(S,Set(T)));A} \\ M. F. Hasler, Nov 30 2018

(A226080(n)=denominator(RabbitOrderedRational(n))); ROR=List(1); RabbitOrderedRational(n)={if(n>#ROR, local(S=Set(ROR), i=#ROR*2\/(sqrt(5)+1), a(t)=setsearch(S,t)||S=setunion(S,[listput(ROR,t)])); until( type(ROR[i+=1])=="t_INT" && n<=#ROR, a(ROR[i]+1); a(1/ROR[i])));ROR[n]} \\ M. F. Hasler, Nov 30 2018

A232559 Sequence (or tree) generated by these rules: 1 is in S, and if x is in S, then x + 1 and 2*x are in S, and duplicates are deleted as they occur.

Original entry on oeis.org

1, 2, 3, 4, 6, 5, 8, 7, 12, 10, 9, 16, 14, 13, 24, 11, 20, 18, 17, 32, 15, 28, 26, 25, 48, 22, 21, 40, 19, 36, 34, 33, 64, 30, 29, 56, 27, 52, 50, 49, 96, 23, 44, 42, 41, 80, 38, 37, 72, 35, 68, 66, 65, 128, 31, 60, 58, 57, 112, 54, 53, 104, 51, 100, 98, 97

Offset: 1

Clark Kimberling, Nov 26 2013

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

			Each x begets x + 1 and 2*x, but if either has already occurred it is deleted.  Thus, 1 begets 2, which begets (3,4); from which 3 begets only 6, and 4 begets (5,8).

Alois P. Heinz, Table of n, a(n) for n = 1..10000 (first 1000 terms from Clark Kimberling)
Katherine E. Stange, The Intuition behind the Double-And-Add / Square-And-Multiply Algorithm, YouTube video, 2021.
Dimitri Zucker, I Found a Simple Pattern That Encodes Different Bases, YouTube video, 2024. (Adds 0 above the root of the tree, and shows how to reconstruct the tree backwards from child nodes)
Robert Munafo, Sequences A232559 and A232561, Spanning Trees of N
Index entries for sequences that are permutations of the natural numbers

Cf. A232560 (inverse permutation), A232561, A232563, A226080, A226130.
Cf. A000045, A026352, A026351, A048679.
Cf. A243571 (rows sorted).
Cf. A014701, A056792.

a:= proc() local l, s; l, s:= [1], {1}:
      proc(n) option remember; local i, r; r:= l[1];
        l:= subsop(1=NULL, l);
        for i in [1+r, r+r] do if not i in s then
          l, s:=[l[], i], s union {i} fi
        od; r
      end
    end():
seq(a(n), n=1..100);  # Alois P. Heinz, Aug 06 2017

z = 12; g[1] = {1}; g[2] = {2}; g[n_] := Riffle[g[n - 1] + 1, 2 g[n - 1]]; j[2] = Join[g[1], g[2]]; j[n_] := Join[j[n - 1], g[n]]; g1[n_] := DeleteDuplicates[DeleteCases[g[n], Alternatives @@ j[n - 1]]]; g1[1] = g[1]; g1[2] = g[2]; t = Flatten[Table[g1[n], {n, 1, z}]]  (* this sequence *)
Table[Length[g1[n]], {n, 1, z}] (* Fibonacci numbers *)
t1 = Flatten[Table[Position[t, n], {n, 1, 200}]]  (* A232560 *)

def aupton(terms):
    alst, S, expand = [1, 2], {1, 2}, [2]
    while len(alst) < terms:
        x = expand.pop(0)
        new_elts = [y for y in [x+1, 2*x] if y not in S]
        alst.extend(new_elts); expand.extend(new_elts); S.update(new_elts)
    return alst[:terms]
print(aupton(66)) # Michael S. Branicky, Sep 14 2021

Conjecture: a(n) = A059894(A348366(n)) for n > 0. - Mikhail Kurkov, Jun 14 2022

A243572 Irregular triangular array generated as in Comments; contains every positive integer exactly once.

Original entry on oeis.org

1, 2, 3, 4, 6, 9, 5, 7, 10, 12, 18, 27, 8, 11, 13, 15, 19, 21, 28, 30, 36, 54, 81, 14, 16, 20, 22, 24, 29, 31, 33, 37, 39, 45, 55, 57, 63, 82, 84, 90, 108, 162, 243, 17, 23, 25, 32, 34, 38, 40, 42, 46, 48, 56, 58, 60, 64, 66, 72, 83, 85, 87, 91, 93, 99, 109

Offset: 1

Clark Kimberling, Jun 07 2014

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.

			First 5 rows of the array:
1
2 ... 3
4 ... 6 ... 9
5 ... 7 ... 10 .. 12 .. 18 .. 27
8 ... 11 .. 13 .. 15 .. 19 .. 21 .. 28 .. 30 .. 36 .. 54 .. 81

Clark Kimberling, Table of n, a(n) for n = 1..1500

Cf. A232561, A243571, A243573, A232561, A002590.

z = 10; g[1] = {1}; f1[x_] := x + 1; f2[x_] := 3 x; h[1] = g[1];
b[n_] := b[n] = DeleteDuplicates[Union[f1[g[n - 1]], f2[g[n - 1]]]];
h[n_] := h[n] = Union[h[n - 1], g[n - 1]];
g[n_] := g[n] = Complement [b[n], Intersection[b[n], h[n]]]
u = Table[g[n], {n, 1, z}]; v = Flatten[u]  (* A243572 *)

cp's OEIS Frontend

A232562 Inverse permutation of the sequence of positive integers at A232561.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A226080 Denominators in the Fibonacci (or rabbit) ordering of the positive rational numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

A232559 Sequence (or tree) generated by these rules: 1 is in S, and if x is in S, then x + 1 and 2*x are in S, and duplicates are deleted as they occur.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A243572 Irregular triangular array generated as in Comments; contains every positive integer exactly once.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica