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

If we insert an initial 1, this is the sequence of numerators in left-hand half of Kepler's tree of fractions. Form a tree of fractions by beginning with 1/1 and then giving every node i/j two descendants labeled i/(i+j) and j/(i+j). See A086592 for denominators. See A294442 for the Kepler tree itself.

Level n of the tree consists of 2^n nodes: 1/2; 1/3, 2/3; 1/4, 3/4, 2/5, 3/5; 1 /5, 4/5, 3/7, 4/7, 2/7, 5/7, 3/8, 5/8; ... Fibonacci numbers occur at the right edge this tree, i.e., a(A000225(n)) = A000045(n+1). The fractions are given in their reduced form, thus gcd(A020650(n), A020651(n)) = 1 and gcd(A020651(n), A086592(n)) = 1 for all n. - Antti Karttunen, May 26 2004

A generalization which includes the "rabbit tree" (A226080) and "all rationals tree" (A226130) follows. Suppose that a,b,c,d,e,f,g,h are complex numbers. Let S be the set of numbers defined by these rules: (1) 1 is in S; (2) if x is in S and cx+d is not 0, then U(x) = (ax+b)/(cx+d) is in S; (3) if x is in S and gx+h is not 0, then D(x) = (ex+f)/(gx+h) is in S. If an infinite path in the resulting tree has convergent nodes, then there is some node after which the path is "updown zigzag" ((UoD)o(UoD)o ...) or "downup zigzag" (DoU)o(DoU)o ...). If ag+ch is not 0, then the updown zigzag limit is invariant of x and equals [ae + cf - bg - dh + sqrt(X)]/(2(ag + ch)), where X = (ae + cf - bg - dh)^2 + 4(be + df + ag + ch). If ce + dg is not 0, then the downup zigzag limit is invariant of x and equals [ae + bg - cf - dh + sqrt(Y)]/(2(ce + dg)), where Y = (ae + bg - cf - dh)^2 + 4(af + bh)(ce + dg)) = X. Thus, for the tree A020651, the updown zigzag limit is -1 + sqrt(2) and the downup zigzag limit, sqrt(2). - Clark Kimberling, Nov 10 2013

From Yosu Yurramendi, Jul 13 2014: (Start)

If the terms (n > 0) are written as an array (left-aligned fashion) with rows of length 2^m, m = 0,1,2,3,...

1,

1,2,

1,3,2,3,

1,4,3,4,2,5,3,5,

1,5,4,5,3,7,4,7,2, 7,5, 7,3, 8,5, 8,

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

then the sum of the m-th row is 3^m (m = 0,1,2,), and each column is an arithmetic sequence. The differences of the arithmetic sequences, except the first on the left, give the sequence A093873 (Numerators in Kepler's tree of harmonic fractions) (a(2^(m+1)-1-k) - a(2^m-1-k) = A093873(k), m = 0,1,2,..., k = 0,1,2,...,2^m-1).

If the rows are written in a right-aligned fashion:

1,

1, 2,

1, 3,2, 3,

1, 4,3, 4,2, 5,3, 5,

1,5,4,5,3, 7,4, 7,2, 7,5, 7,3, 8,5, 8,

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

then each column k is a Fibonacci sequence. (End)

For m >= 0, a(2^m) = 1 and a(3*2^m) = 2. For n >= 0, a(A070875(n)) = 3 (for m >= 0, a(5*2^m) = 3 and a(7*2^m) = 3). - Yosu Yurramendi, Jun 02 2016

Let S be the set of numbers defined by these rules: 1 is in S, and if nonzero x is in S, then x + 1 and -1/x are in S. Then S is the set of all rational numbers, produced in generations as follows: g(1) = (1), g(2) = (2, -1), g(3) = (3, -1/2, 0), g(4) = (4, -1/3, 1/2), ... For n > 4, once g(n-1) = (c(1), ..., c(z)) is defined, g(n) is formed from the vector (c(1)+1, -1/c(1), c(2)+1, -1/c(2), ..., c(z)+1, -1/c(z)) by deleting previously generated elements. Let S' denote the sequence formed by concatenating the generations.

A226130: Denominators of terms of S'

A226131: Numerators of terms of S'

A226136: Positions of positive integers in S'

A226137: Positions of integers in S'

The length of row n is given by A226275(n-1). - Peter Kagey, Jan 17 2022

See Comments at A245215.

Likely a duplicate of A097509. - R. J. Mathar, Jul 21 2014

Theorem: Referring to Problem B6 in the 81st William Lowell Putnam Mathematical Competition (see link), in the notation of the first solution, the sequence {c_i} equals A245219. This proves the conjecture in the previous comment. - Manjul Bhargava, Kiran Kedlaya, and Lenny Ng, Sep 09 2021.

The Zeckendorf distance between positive integers m and n is defined as follows. Suppose that n = F(i1) + F(i2) + ... F(ij) is the Zeckendorf representation of n, where 1 is represented as F(1), not F(2). Let d(n) = F(i1 - 1) + F(i2 - 1) + ... + F(ij - 1); i.e., the indexes for n are downshifted to form d(n). Starting with any n, the number of arrows in the graph n -> d(n) -> d(d(n)) -> ... -> 1 is the "generation number" of n; write the k-th node as s(k,n). If m and n are positive integers, let K(m) and K(n) be the numbers for which s(K(m),m) = s(K(n),n). This first common ancestor, or root, of m and n is denoted r(m,n). The distance between m and n is D(m,n) = K(m) + K(n).

It is helpful to regard m and n as nodes in a "Zeckendorf tree" rooted a 1 with edges given by successive upshifting of indexes of Zeckendorf representations; then D(m,n) is the number of edges from m to n. Equivalently, one can start with the Fibonacci (or rabbit) tree of the positive rational numbers (A226080). Replacing each fraction in the tree by its position when the elements are arranged in the order in which generated gives the Zeckendorf array. Thus, D is not only the Zeckendorf graph metric for positive integers, but is also, isomorphically speaking, a graph metric for the positive rational numbers.

Suppose that b(n) and c(n) are sequences of positive integers. Sequences D(b(n),c(n)), with exceptions for first terms in some cases, are indicated here:

....

D(b(n),c(n)) ... b(n) ........ c(n)

A000012 ........ F(n) ........ F(n+1), consecutive Fibonacci numbers

A005408 ........ F(n) ........ L(n), Fibonacci(n) and Lucas(n)

A095791 ........ 1 ........... n

A000012 ........ A000201(n) .. A001950(n), the Wythoff sequences

A226208 ........ n ........... n+1

A226209 ........ n ........... n+2

A226210 ........ n............ F(n)

A226211 ........ n............ 2n

A226212 ........ n............ floor(n/2)

A226213 ........ n............ 2^n

A226214 ........ n............ n^2

A226215 ........ n! .......... (n+1)!

Equivalently, f(n,x) = 1/(f(n-1,x) if n is in A001950 (upper Wythoff sequence, given by w(n) = floor[tau*n], where tau = (1 + sqrt(5))/2, the golden ratio) and f(n,x) = f(n-1) + 1 otherwise. Let c = inf{f(n,1)}. The continued fraction of c is [0,2,1,2,1,2,2,1,2,2,1,2, ...], and the continued fraction of sup{f(n,x)}, alias -2 + 1/c, appears to be identical to the Hofstadter eta-sequence at A006340: (2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2,...). Other limiting constants are similarly obtained using other pairs of Beatty sequences:

...

Beatty sequence .... inf{f(n,1)} ... sup{f(n,1)}

A000201 (tau) ...... A245215 ....... A245216

A001951 (sqrt(2)) .. A245217 ....... A245218; cont. fr. A245219

A022838 (sqrt(3)) .. A245220 ....... A245221; cont. fr. A245222

A054385 (e/(e-1)) .. A245223 ....... A245224; cont. fr. A245225

See Comments at A245215.

Let S be the set of numbers defined by these rules: 0 is in S; if x is in S, then x+1 is in S, and if nonzero x is in S, then -1/x are in S. Then S is the set of all rational numbers, produced in generations as follows:

g(1) = (0), g(2) = (1), g(3) = (2, -1), g(4) = (3, -1/2), g(5) = (4, -1/3, 1/2), ... For n > 2, once g(n-1) = (c(1), ..., c(z)) is defined, g(n) is formed from the vector (c(1)+1, -1/c(1), c(2)+1, -1/c(2), ..., c(z)+1, -1/c(z)) by deleting previously generated elements.

Let S'' denote the sequence formed by concatenating the generations.

A226247: Denominators of terms of S''

A226248: Numerators of terms of S''

A226249: Positions of nonnegative numbers in S''

A226250: Positions of positive numbers in S''

A closely related sequence S' (for which the rules of generation are shorter but the resulting sequence is slightly less natural) is discussed at A226130. For both S' and S'', the number of numbers in g(n) is given by A097333.

See Comments at A245215.

Appears to be the same as the sequence 1 + [x == 0 (mod sqrt(3))], as x runs over the elements of N U N*sqrt(3) in increasing order, where N = {0, 1, 2, 3, ...} and [...] is the Iverson bracket. - M. F. Hasler, Feb 06 2025

Let S be the set of numbers defined by these rules: 1 is in S, and if nonzero x is in S, then x + 1 and -1/x are in S. Then S is the set of all rational numbers, produced in generations as follows: g(1) = (1), g(2) = (2, -1), g(3) = (3, -1/2, 0), g(4) = (4, -1/3, 1/2), ... For n > 4, once g(n-1) = (c(1), ..., c(z)) is defined, g(n) is formed from the vector (c(1)+1, -1/c(1), c(2)+1, -1/c(2), ..., c(z)+1, -1/c(z)) by deleting previously generated elements.

Let S' denote the sequence formed by concatenating the generations.

A226130: Denominators of terms of S'

A226131: Numerators of terms of S'

A226136: Positions of positive integers in S'

A226137: Positions of integers in S'