cp's OEIS Frontend

a(n) gives the position of the inverse of the n-th term in the full Stern-Brocot tree: A007305(a(n)+2) = A047679(n) and A047679(a(n)) = A007305(n+2). - Reinhard Zumkeller, Dec 22 2008

From Gary W. Adamson, Jun 21 2012: (Start)

The mapping and conversion rules are as follows:

By rows, we have ...

1;

3, 2;

7, 6, 5, 4;

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

... onto which we are to map one-half of the Stern-Brocot infinite Farey Tree:

1/2

1/3, 2/3

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

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

...

The conversion rules are: Convert the decimal to binary, adding a duplicate of the rightmost binary term to its right. For example, 10 = 1010, which becomes 10100. Then, from the left, record the number of runs = [1,1,1,2], the continued fraction representation of 5/8. Check: 10 decimal corresponds to 5/8 as shown in the overlaid mapping. Take decimal 9 = 1001 which becomes 10011, with a continued fraction representation of [1,2,2] = 5/7. Check: 9 decimal corresponds to 5/7 in the Farey Tree map. (End)

From Indranil Ghosh, Jan 19 2017: (Start)

a(n) is the value generated when n is converted into its Elias gamma code, the 1's and 0's are interchanged and the resultant is converted back to its decimal value for all values of n > 1. For n = 1, A054429(n) = 1 but after converting 1 to Elias gamma code, interchanging the 1's and 0's and converting it back to decimal, the result produced is 0.

For example, let n = 10. The Elias gamma code for 10 is '1110010'. After interchanging the 1's and 0's it becomes "0001101" and 1101_2 = 13_10. So a(10) = 13. (End)

From Yosu Yurramendi, Mar 09 2017 (similar to Zumkeller's comment): (Start)

A002487(a(n)) = A002487(n+1), A002487(a(n)+1) = A002487(n), n > 0.

A162909(a(n)) = A162910(n), A162910(a(n)) = A162909(n), n > 0.

A162911(a(n)) = A162912(n), A162912(a(n)) = A162911(n), n > 0.

A071766(a(n)) = A245326(n), A245326(a(n)) = A071766(n), n > 0.

A229742(a(n)) = A245325(n), A245325(a(n)) = A229742(n), n > 0.

A020651(a(n)) = A245327(n), A245327(a(n)) = A020651(n), n > 0.

A020650(a(n)) = A245328(n), A245328(a(n)) = A020650(n), n > 0. (End)

From Yosu Yurramendi, Mar 29 2017: (Start)

A063946(a(n)) = a(A063946(n)) = A117120(n), n > 0.

A065190(a(n)) = a(A065190(n)) = A092569(n), n > 0.

A258746(a(n)) = a(A258746(n)) = A165199(n), n > 0.

A258996(a(n)) = a(A258996(n)), n > 0.

A117120(a(n)) = a(A117120(n)), n > 0.

A092569(a(n)) = a(A092569(n)), n > 0. (End)

A self-inverse permutation of the natural numbers.

a(n)=n if and only if A081242(n) is a palindrome. - Clark Kimberling, Mar 12 2003

a(n) is the position in B of the reversal of the n-th term of B, where B is the left-to-right binary enumeration sequence (A081242 with the empty word attached as first term). - Clark Kimberling, Mar 12 2003

From Antti Karttunen, Oct 28 2001: (Start)

When certain Stern-Brocot tree-related permutations are conjugated with this permutation, they induce a permutation on Z (folded to N), which is an infinite siteswap permutation (see, e.g., figure 7 in the Buhler and Graham paper, which is permutation A065174). We get:

A065260(n) = a(A057115(a(n))),

A065266(n) = a(A065264(a(n))),

A065272(n) = a(A065270(a(n))),

A065278(n) = a(A065276(a(n))),

A065284(n) = a(A065282(a(n))),

A065290(n) = a(A065288(a(n))). (End)

Every nonnegative integer has a unique representation c(1) + c(2)*2 + c(3)*2^2 + c(4)*2^3 + ..., where every c(i) is 0 or 1. Taking tuples of coefficients in lexical order (i.e., 0, 1; 01,11; 001,011,101,111; ...) yields A059893. - Clark Kimberling, Mar 15 2015

From Ed Pegg Jr, Sep 09 2015: (Start)

The reduced rationals can be ordered either as the Calkin-Wilf tree A002487(n)/A002487(n+1) or the Stern-Brocot tree A007305(n+2)/A047679(n). The present sequence gives the order of matching rationals in the other sequence.

For reference, the Calkin-Wilf tree is 1, 1/2, 2, 1/3, 3/2, 2/3, 3, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4, 1/5, 5/4, 4/7, 7/3, 3/8, 8/5, 5/7, 7/2, 2/7, 7/5, 5/8, 8/3, 3/7, 7/4, 4/5, ..., which is A002487(n)/A002487(n+1).

The Stern-Brocot tree is 1, 1/2, 2, 1/3, 2/3, 3/2, 3, 1/4, 2/5, 3/5, 3/4, 4/3, 5/3, 5/2, 4, 1/5, 2/7, 3/8, 3/7, 4/7, 5/8, 5/7, 4/5, 5/4, 7/5, 8/5, 7/4, 7/3, 8/3, 7/2, ..., which is A007305(n+2)/A047679(n).

There is a great little OEIS-is-useful story here. I had code for the position of fractions in the Calkin-Wilf tree. The best I had for positions of fractions in the Stern-Brocot tree was the paper "Locating terms in the Stern-Brocot tree" by Bruce Bates, Martin Bunder, Keith Tognetti. The method was opaque to me, so I used my Calkin-Wilf code on the Stern-Brocot fractions, and got A059893. And thus the problem was solved. (End)

a(n) appears on row 1 of the array illustrated in A066099.

Except for initial zero, ordinal transform of A062050. After initial zero, n-th chunk consists of n, one n-1, two (n-2)'s, ..., 2^(k-1) (n-k)'s, ..., 2^(n-1) 1's. - Franklin T. Adams-Watters, Sep 11 2006

Zero together with a triangle read by rows in which row j lists the first 2^(j-1) terms of A001511 in nonincreasing order, j >= 1, see example. Also row j lists the first parts, in nonincreasing order, of the compositions of j. - Omar E. Pol, Sep 11 2013

The n-th row represents the frequency distribution of 1, 2, 3, ..., 2^(n-1) in the first 2^n - 1 terms of A003602. - Gary W. Adamson, Jun 10 2021

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

This permutation is induced by a wreath recursion a = s(a,b), b = (b,b) (i.e., binary transducer, where s means that the bits at that state are toggled: 0 <-> 1) given on page 103 of the Bondarenko, Grigorchuk, et al. paper, starting from the active (swapping) state a and rewriting bits from the second most significant bit to the least significant end, continuing complementing as long as the first 1-bit is reached, which is the last bit to be complemented.

The automorphism group of infinite binary tree (isomorphic to an infinitely iterated wreath product of cyclic groups of two elements) embeds naturally into the group of "size-preserving Catalan bijections". Scheme-function psi gives an isomorphism that maps this kind of permutation to the corresponding Catalan automorphism/bijection (that acts on S-expressions). The following identities hold: *A069770 = psi(A063946) (just swap the left and right subtrees of the root), *A057163 = psi(A054429) (reflect the whole tree), *A069767 = psi(A153141), *A069768 = psi(A153142), *A122353 = psi(A006068), *A122354 = psi(A003188), *A122301 = psi(A154435), *A122302 = psi(A154436) and from *A154449 = psi(A154439) up to *A154458 = psi(A154448). See also comments at A153246 and A153830.

a(1) to a(2^n) is the sequence of row sequency numbers in a Hadamard-Walsh matrix of order 2^n, when constructed to give "dyadic" or Payley sequency ordering. - Ross Drewe, Mar 15 2014

In the Stern-Brocot enumeration system for positive rationals (A007305/A047679), this permutation converts the denominator into the numerator: A007305(n) = A047679(a(n)). - Yosu Yurramendi, Aug 01 2020

a(0) could be considered to be 0 if the binary representation of zero were chosen to be the empty string. - Jason Kimberley, Sep 19 2011

From Bernard Schott, Jun 15 2021: (Start)

Except for a(0) = 1, every term is even.

For each q >= 0, there is one and only one odd number h such that a(n) = 2*q iff n = h*2^m-1 for m >= 1 when q = 0, and for m >= 0 when q >= 1 (see A345401 and some examples below).

a(n) = 0 iff n = 2^m-1 for m >= 1 (Mersenne numbers) (A000225).

a(n) = 2 iff n = 3*2^m-1 for m >= 0 (A153893).

a(n) = 4 iff n = 7*2^m-1 for m >= 0 (A086224).

a(n) = 6 iff n = 5*2^m-1 for m >= 0 (A153894).

a(n) = 8 iff n = 15*2^m-1 for m >= 0 (A196305).

a(n) = 10 iff n = 11*2^m-1 for m >= 0 (A086225).

a(n) = 12 iff n = 13*2^m-1 for m >= 0 (A198274).

For k >= 1, a(n) = 2^k iff n = (2^(k+1)-1)*2^m - 1 for m >= 0.

Explanation for a(n) = 2:

For m >= 0, A153893(m) = 3*2^m-1 -> 1011...11 -> 0100...00 -> 10 -> 2 where 1011...11_2 is 10 followed by m 1's. (End)

Conjecture: For all n, a(A054429(n)) = A054429(a(n)), i.e. A054429 acts as a homomorphism (automorphism) of the cyclic group generated by this permutation. This implies also a weaker conjecture given in A209860.

From Gus Wiseman, Aug 24 2021: (Start)

As a triangle with row lengths 2^n, T(n,k) for n > 0 appears (verified up to n = 2^15) to be the unique nonnegative integer whose binary indices are the k-th subset of {1..n} containing n. Here, a binary index of n (row n of A048793) is any position of a 1 in its reversed binary expansion, and sets are sorted first by length, then lexicographically. For example, the triangle begins:

1

2 3

4 5 6 7

8 9 10 12 11 13 14 15

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

Mathematica: Table[Total[2^(Append[#,n]-1)]&/@Subsets[Range[n-1]],{n,5}]

Row lengths are A000079 (shifted right). Also Column k = 1.

Row sums are A010036.

Using reverse-lexicographic order gives A059893.

Using lexicographic order gives A059894.

Taking binary indices to prime indices gives A339195 (or A019565).

The ordering of sets is A344084.

A version using Heinz numbers is A344085.

(End)

This sequence and A341392 have the same set of values on intervals from 2^m to 2^(m+1) - 1 for m >= 0. - Mikhail Kurkov, Jun 18 2021 [verification needed]

Thus a(n)/a(m) = d_1 + 1/(d_2 + 1/(d_3 + ... + 1/d_k)) where m = n - 2^floor(log_2(n)) + 1 and where d_j = b_j - b_(j+1) are the differences of the binary exponents b_j > b_(j+1) defined by: 4*n = 2^b_1 + 2^b_2 + 2^b_3 + ... 2^b_k.

All the rationals are uniquely represented by this sequence - compare Stern's diatomic sequence A002487.

This sequence lists the rationals >= 1 in order by the sum of the terms of their continued fraction expansions. For example, the numerators generated from partitions of 5 that do not end with 1 are listed together as 5, 7, 7, 8, 5, 7, 7, 8, since: 5/1 = [5]; 7/2 = [3;2]; 7/3 = [2;3]; 8/3 = [2;1,2]; 5/4 = [1;4]; 7/5 = [1;2,2]; 7/4 = [1;1,3]; 8/5 = [1;1,1,2].

From Yosu Yurramendi, Jun 23 2014: (Start)

If the terms (n>0) are written as an array:

1,

2,

3, 3,

4, 5, 4, 5,

5, 7, 7, 8, 5, 7, 7, 8,

6, 9,10,11, 9,12,11,13, 6, 9,10,11, 9,12,11,13,

7,11,13,14,13,17,15,18,11,16,17,19,14,19,18,21,7,11,13,14,13,17,15,18,11, ...

then the sum of the k-th row is 2*3^(k-2) for k>1, each column is an arithmetic progression. The differences of the arithmetic sequences give the sequence A071585 itself: a(2^(p+1)+k) - a(2^p+k) = a(k). A002487 and A007306 also have these properties. The first terms of columns, excluding a(0), give A086593.

If the rows (n>0) are written on right:

1;

2;

3, 3;

4, 5, 4, 5;

5, 7, 7, 8, 5, 7, 7, 8;

6, 9, 10, 11, 9, 12, 11, 13, 6, 9, 10, 11, 9, 12, 11, 13;

then each column is a Fibonacci sequence: a(2^(p+2)+k) = a(2^(p+1)+k) + a(2^p+k). The first terms of columns, excluding a(0), give A086593. (End)

n>1 occurs in this sequence phi(n) = A000010(n) times, as it occurs in A007306 (Franklin T. Adams-Watters's comment), that is the sequence obtained by adding numerator and denominator in the Calkin-Wilf enumeration system of positive rationals. A229742(n)/A071766(n) is also an enumeration system of all positive rationals (HCS system), and in each level m >= 0 (ranks between 2^m and 2^(m+1)-1) rationals are the same in both systems. Thus a(n) (A229742(n)+A071766(n)) has the same terms in each level as A007306. The same property occurs in all numerator+denominator sequences of enumeration systems of positive rationals, as, for example, A007306 (A007305+A047679), A086592 (A020650+A020651), and A268087 (A162909+A162910). - Yosu Yurramendi, Apr 06 2016

a(n) = A086592(A059893(n)), a(A059893(n)) = A086592(n), n > 0. - Yosu Yurramendi, May 30 2017

This sequence can be also obtained by starting complementing n's binary expansion from the second most significant bit, continuing towards lsb-end until the first 0-bit is reached, which is the last bit to be complemented.

In the Stern-Brocot enumeration system for positive rationals (A007305/A047679), this permutation converts the numerator into the denominator: A047679(n) = A007305(a(n)). - Yosu Yurramendi, Aug 30 2020