A057115 -id:A057115 - cp's OEIS frontend

A065260 A057115 conjugated with A059893, inverse of A065259.

2, 4, 1, 8, 6, 12, 3, 16, 10, 20, 5, 24, 14, 28, 7, 32, 18, 36, 9, 40, 22, 44, 11, 48, 26, 52, 13, 56, 30, 60, 15, 64, 34, 68, 17, 72, 38, 76, 19, 80, 42, 84, 21, 88, 46, 92, 23, 96, 50, 100, 25, 104, 54, 108, 27, 112, 58, 116, 29, 120, 62, 124, 31, 128, 66, 132, 33, 136, 70

Offset: 1

Antti Karttunen, Oct 28 2001

This permutation of N induces also such permutation of Z, that p(i)-i >= 0 for all i.

			G.f. = 2*x + 4*x^2 + x^3 + 8*x^4 + 6*x^5 + 12*x^6 + 3*x^7 + 16*x^8 + ...

Colin Barker, Table of n, a(n) for n = 1..1000
Joe Buhler and R. L. Graham, Juggling Drops and Descents, Amer. Math. Monthly, 101, (no. 6) 1994, 507 - 519.
Index entries for sequences that are permutations of the natural numbers
Index entries for linear recurrences with constant coefficients, signature (0,0,0,2,0,0,0,-1).

Cf. also A065171. The siteswap sequence (deltas) is A065261.

Vec(x*(2+4*x+x^2+8*x^3+2*x^4+4*x^5+x^6)/((1-x)^2*(1+x)^2*(1+x^2)^2) + O(x^100)) \\ Colin Barker, Oct 29 2016

{a(n) = if( n%2==0, n*2, n%4==1, n+1, n\2)}; /* Michael Somos, Nov 06 2016 */

a(n) = A059893(A057115(A059893(n))).
a(2*k+2) = 4*k+4, a(4*k+1) = 4*k+2, a(4*k+3) = 2*k+1. - Ralf Stephan, Jun 10 2005
G.f.: x*(x^6+4*x^5+2*x^4+8*x^3+x^2+4*x+2) / ((x-1)^2*(x+1)^2*(x^2+1)^2). - Colin Barker, Feb 18 2013
a(n) = 2*a(n-4) - a(n-8) for n>8. - Colin Barker, Oct 29 2016
a(n) = (11*n+1+(5*n-1)*(-1)^n-(n+3)*(1-(-1)^n)*(-1)^((2*n+3+(-1)^n)/4))/8. - Luce ETIENNE, Oct 20 2016

A059893 Reverse the order of all but the most significant bit in binary expansion of n: if n = 1ab..yz then a(n) = 1zy..ba.

Original entry on oeis.org

1, 2, 3, 4, 6, 5, 7, 8, 12, 10, 14, 9, 13, 11, 15, 16, 24, 20, 28, 18, 26, 22, 30, 17, 25, 21, 29, 19, 27, 23, 31, 32, 48, 40, 56, 36, 52, 44, 60, 34, 50, 42, 58, 38, 54, 46, 62, 33, 49, 41, 57, 37, 53, 45, 61, 35, 51, 43, 59, 39, 55, 47, 63, 64, 96, 80, 112, 72, 104, 88, 120

Offset: 1

Marc LeBrun, Feb 06 2001

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(11) = a(1011) = 1110 = 14.
With empty word e prefixed, A081242 becomes (e,1,2,11,21,12,22,111,211,121,221,112,...); (reversal of term #9) = (term #12); i.e., a(9)=12 and a(12)=9. - _Clark Kimberling_, Mar 12 2003
From _Philippe Deléham_, Jun 02 2015: (Start)
This sequence regarded as a triangle with rows of lengths 1, 2, 4, 8, 16, ...:
   1;
   2,  3;
   4,  6,  5,  7;
   8, 12, 10, 14,  9,  13,  11,  15;
  16, 24, 20, 28, 18,  26,  22,  30,  17,  25,  21,  29,  19,  27,  23,  31;
  32, 48, 40, 56, 36,  52,  44, ...
Row sums = A010036. (End)

Alois P. Heinz, Table of n, a(n) for n = 1..8191 (first 1023 terms from T. D. Noe)
Bruce Bates, Martin Bunder, and Keith Tognetti, Locating terms in the Stern-Brocot tree, European Journal of Combinatorics 31.3 (2010): 1020-1033.
Joe Buhler and R. L. Graham, Juggling Drops and Descents, Amer. Math. Monthly, 101, (no. 6) 1994, 507-519.
Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang, Finding structure in sequences of real numbers via graph theory: a problem list, arXiv:2012.04625, 2020-2021.
Wikipedia, Calkin-Wilf Tree.
Wikipedia, Stern-Brocot tree.
Index entries for sequences related to Stern's sequences
Index entries for sequences that are permutations of the natural numbers

{A000027, A054429, A059893, A059894} form a 4-group.
The set of permutations {A059893, A080541, A080542} generates an infinite dihedral group.
Cf. A000079, A000523, A007931, A030308.
In other bases: A351702 (balanced ternary), A343150 (Zeckendorf), A343152 (lazy Fibonacci).

a059893 = foldl (\v b -> v * 2 + b) 1 . init . a030308_row
-- Reinhard Zumkeller, May 01 2013
(Scheme, with memoization-macro definec)
(definec (A059893 n) (if (<= n 1) n (let* ((k (- (A000523 n) 1)) (r (A059893 (- n (A000079 k))))) (if (= 2 (floor->exact (/ n (A000079 k)))) (* 2 r) (+ 1 r)))))
;; Antti Karttunen, May 16 2015

# Implements Bottomley's formula
A059893 := proc(n) option remember; local k; if(1 = n) then RETURN(1); fi; k := floor_log_2(n)-1; if(2 = floor(n/(2^k))) then RETURN(2*A059893(n-(2^k))); else RETURN(1+A059893(n-(2^k))); fi; end;
floor_log_2 := proc(n) local nn,i; nn := n; for i from -1 to n do if(0 = nn) then RETURN(i); fi; nn := floor(nn/2); od; end;
# second Maple program:
a:= proc(n) local i, m, r; m, r:= n, 0;
      for i from 0 while m>1 do r:= 2*r +irem(m,2,'m') od;
      r +2^i
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Feb 28 2015

A059893 = Reap[ For[n=1, n <= 100, n++, a=1; b=n; While[b > 1, a = 2*a + 2*FractionalPart[b/2]; b=Floor[b/2]]; Sow[a]]][[2, 1]] (* Jean-François Alcover, Jul 16 2012, after Harry J. Smith *)
ro[n_]:=Module[{idn=IntegerDigits[n,2]},FromDigits[Join[{First[idn]}, Reverse[ Rest[idn]]],2]]; Array[ro,80] (* Harvey P. Dale, Oct 24 2012 *)

a(n) = my(b=binary(n)); fromdigits(concat(b[1], Vecrev(vector(#b-1, k, b[k+1]))), 2); \\ Michel Marcus, Sep 29 2021

def a(n): return int('1' + bin(n)[3:][::-1], 2)
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Mar 21 2017

maxrow <- 6 # by choice
a <- 1
for(m in 0:maxrow) for(k in 0:(2^m-1)) {
  a[2^(m+1)+    k] <- 2*a[2^m+k]
  a[2^(m+1)+2^m+k] <- 2*a[2^m+k] + 1
}
a
# Yosu Yurramendi, Mar 20 2017

maxblock <- 7 # by choice
a <- 1
for(n in 2:2^maxblock){
  ones <- which(as.integer(intToBits(n)) == 1)
  nbit <- as.integer(intToBits(n))[1:tail(ones, n = 1)]
  anbit <- nbit
  anbit[1:(length(anbit) - 1)] <- anbit[rev(1:(length(anbit)-1))]
  a <- c(a, sum(anbit*2^(0:(length(anbit) - 1))))
}
a
# Yosu Yurramendi, Apr 25 2021

a(n) = A030109(n) + A053644(n). If 2*2^k <= n < 3*2^k then a(n) = 2*a(n-2^k); if 3*2^k <= n < 4*2^k then a(n) = 1 + a(n-2^k) starting with a(1)=1. - Henry Bottomley, Sep 13 2001

A057114 Permutation of N induced by the order-preserving permutation of the rational numbers (x -> x+1); positions in Stern-Brocot tree.

Original entry on oeis.org

3, 1, 7, 2, 6, 14, 15, 4, 5, 12, 13, 28, 29, 30, 31, 8, 9, 10, 11, 24, 25, 26, 27, 56, 57, 58, 59, 60, 61, 62, 63, 16, 17, 18, 19, 20, 21, 22, 23, 48, 49, 50, 51, 52, 53, 54, 55, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 96, 97, 98, 99, 100, 101, 102, 103

Offset: 1

Antti Karttunen, Aug 09 2000

nonn

The "unbalancing operation" used here is what is usually called "rotation of binary trees" (e.g. in Lucas, Ruskey et al. article)

			Consider the following "extended" Stern-Brocot tree (on interval ]-inf,inf[):
....................................0/1
.................-1/1.................................1/1
......-2/1................-1/2...............1/2...............2/1
.-3/1......-3/2......-2/3......-1/3.....1/3.......2/3.....3/2.......3/1
Enumerate the fractions breadth-first (0/1 = 1, -1/1 = 2, 1/1 = 3, -2/1 = 4, -1/2 = 5, etc.) then use this sequence to pick third, first, 7th, 2nd, etc. fractions. We get a bijection (0/1 -> 1/1, -1/1 -> 0/1, 1/1 -> 2/1, -2/1 -> -1/1, -1/2 -> 1/2, etc.) which is the function x -> x+1.
In other words, we cut the edge between 1/1 and 1/2, make 1/1 the new root and create a new edge between 0/1 and 1/2 to get an "unbalanced" Stern-Brocot tree. If we instead make a similar change to subtree 1/1 (cut {2/1,3/2}, create {1/1,3/2} and make 2/1 the new root of the positive side, leaving the negative side as it is), we get the function given in Maple procedure sbtree_perm_1_1_right.
Both mappings belong to Cameron's group "A" of permutations of the rational numbers which preserve their linear order and by applying such unbalancing operations successively (possibly infinitely many times) to the "extended" Stern-Brocot tree given above, the whole group "A" can be generated.

Joan Lucas, Dominique Roelants van Baronaigien and Frank Ruskey, On Rotations and the Generation of Binary Trees, Journal of Algorithms, 15 (1993) 343-366.

A. Bogomolny, About the Stern-Brocot tree
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Index entries for sequences related to Stern's sequences
Index entries for sequences that are permutations of the natural numbers

SternBrocotNum given in A007305, SternBrocotDen in A047679, frac2position_in_whole_SB_tree in A054424. Inverse permutation: A057115. Cf. also A065249 and A065250.
A065259(n) = A059893(A057114(A059893(n)))
The first row of A065625, i.e. a(n) = RotateNodeRight(1, n).

sbtree_perm_1_1_right := x -> (`if`((x <= 0),x,(`if`((x < (1/2)),(x/(1-x)),(`if`((x < 1),(3-(1/x)),(x+1)))))));

a(n) = frac2position_in_whole_SB_tree (sbtree_perm_1_1_right (SternBrocotTreeNum(n) / SternBrocotTreeDen(n))).

A065626 Table of permutations of N, each row being a generator of the "rotation group" of infinite planar binary tree. Inverse generators are given in A065625.

Original entry on oeis.org

2, 4, 1, 1, 4, 1, 8, 3, 2, 1, 9, 8, 6, 2, 1, 5, 2, 4, 3, 2, 1, 3, 6, 5, 8, 3, 2, 1, 16, 7, 12, 5, 4, 3, 2, 1, 17, 16, 3, 6, 10, 4, 3, 2, 1, 18, 17, 8, 7, 6, 5, 4, 3, 2, 1, 19, 9, 9, 16, 7, 12, 5, 4, 3, 2, 1, 10, 5, 10, 4, 8, 7, 6, 5, 4, 3, 2, 1, 11, 12, 11, 10, 9, 8, 14, 6, 5, 4, 3, 2, 1, 6, 13, 24, 11, 20, 9, 8, 7, 6, 5, 4, 3, 2, 1, 7, 14, 25, 12, 5, 10, 9, 16, 7, 6, 5, 4, 3, 2

Offset: 0

Antti Karttunen, Nov 08 2001

The first row (rotate the top node left): A057115, 2nd row (rotate the top node's left child): A065628, 3rd row (rotate the top node's right child): A065630, 4th row: A065632, 5th row: A065634, 6th row: A065636, 7th row: A065638, 8th row: A065640. Maple procedure floor_log_2 given in A054429, for trinv, follow A065167.

[seq(RotateLeftTable(j),j=0..119)];
RotateLeftTable := n -> RotateNodeLeft(1+(n-((trinv(n)*(trinv(n)-1))/2)),(((trinv(n)-1)*(((1/2)*trinv(n))+1))-n)+1);
# Rewrites t-prefixed x's in the following way: t -> t0, t0... -> t00..., t1 -> t, t10... -> t01..., t11... -> t1... and leaves other x's intact.
RotateNodeLeft := proc(t,x) local u,y; u := floor_log_2(t)+1; y := floor_log_2(x)+1; if(y < u) then RETURN(x); fi; if(floor(x/(2^(y-u))) <> t) then RETURN(x); fi; if(x = t) then RETURN(2*x); fi; if(0 = (floor(x/(2^(y-u-1))) mod 2)) then RETURN(x + (t * 2^(y-u))); fi; if(y = (u+1)) then RETURN((x-1)/2); fi; if(0 = (floor(x/(2^(y-u-2))) mod 2)) then RETURN(x - 2^(y-u-2)); fi; RETURN(x - ((t+1) * 2^(y-u-1))); end;

A065627 Permutation of N induced by rotating the node 2 right in the infinite planar binary tree. The second row of A065625. Inverse of A065628.

Original entry on oeis.org

1, 5, 3, 2, 11, 6, 7, 4, 10, 22, 23, 12, 13, 14, 15, 8, 9, 20, 21, 44, 45, 46, 47, 24, 25, 26, 27, 28, 29, 30, 31, 16, 17, 18, 19, 40, 41, 42, 43, 88, 89, 90, 91, 92, 93, 94, 95, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 32, 33, 34, 35, 36, 37, 38, 39, 80, 81, 82, 83, 84, 85, 86, 87, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186

Offset: 1

Antti Karttunen, Nov 08 2001

nonn

Index entries for sequences that are permutations of the natural numbers

A065627[n] = A057114[A065631[A057115[n]]]. Stabilizes the set A004760.

Maple
```
[seq(RotateNodeRight(2,j),j=1..120)];
```

A065631 Permutation of N induced by rotating the node 4 right in the infinite planar binary tree. The fourth row of A065625. Inverse of A065632.

Original entry on oeis.org

1, 2, 3, 9, 5, 6, 7, 4, 19, 10, 11, 12, 13, 14, 15, 8, 18, 38, 39, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 16, 17, 36, 37, 76, 77, 78, 79, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 32, 33, 34, 35, 72, 73, 74, 75, 152, 153, 154, 155, 156, 157, 158, 159, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91

Offset: 1

Antti Karttunen, Nov 08 2001

nonn

Index entries for sequences that are permutations of the natural numbers

A065631[n] = A057115[A065627[A057114[n]]]

Maple
```
[seq(RotateNodeRight(4,j),j=1..120)];
```

A065637 Permutation of N induced by rotating the node 7 right in the infinite planar binary tree. The seventh row of A065625. Inverse of A065638.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 15, 8, 9, 10, 11, 12, 13, 7, 31, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 14, 30, 62, 63, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 28, 29, 60, 61, 124, 125, 126, 127, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92

Offset: 1

Antti Karttunen, Nov 08 2001

nonn

Index entries for sequences that are permutations of the natural numbers

A065637[n] = A057114[A065629[A057115[n]]]

Maple
```
[seq(RotateNodeRight(7,j),j=1..120)];
```

A065639 Permutation of N induced by rotating the node 8 right in the infinite planar binary tree. The eighth row of A065625. Inverse of A065640.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 17, 9, 10, 11, 12, 13, 14, 15, 8, 35, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 16, 34, 70, 71, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 32, 33, 68, 69, 140, 141, 142, 143, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92

Offset: 1

Antti Karttunen, Nov 08 2001

nonn

Index entries for sequences that are permutations of the natural numbers

A065639[n] = A057115[A065631[A057114[n]]] = A057115[A057115[A065627[A057114[A057114[n]]]]]

Maple
```
[seq(RotateNodeRight(8,j),j=1..120)];
```

A065640 Permutation of N induced by rotating the node 8 left in the infinite planar binary tree. The eighth row of A065626. Inverse of A065639.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 16, 9, 10, 11, 12, 13, 14, 15, 32, 8, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 64, 65, 33, 17, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 128, 129, 130, 131, 66, 67, 34, 35, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92

Offset: 1

Antti Karttunen, Nov 08 2001

nonn

Index entries for sequences that are permutations of the natural numbers

A065640[n] = A057115[A065632[A057114[n]]] = A057115[A057115[A065628[A057114[A057114[n]]]]]

Maple
```
[seq(RotateNodeLeft(8,j),j=1..120)];
```

cp's OEIS Frontend

A065260 A057115 conjugated with A059893, inverse of A065259.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

A059893 Reverse the order of all but the most significant bit in binary expansion of n: if n = 1ab..yz then a(n) = 1zy..ba.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

R

R

Formula

A057114 Permutation of N induced by the order-preserving permutation of the rational numbers (x -> x+1); positions in Stern-Brocot tree.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

A065626 Table of permutations of N, each row being a generator of the "rotation group" of infinite planar binary tree. Inverse generators are given in A065625.

Views

Author

Keywords

Crossrefs

Programs

Maple

A065627 Permutation of N induced by rotating the node 2 right in the infinite planar binary tree. The second row of A065625. Inverse of A065628.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A065631 Permutation of N induced by rotating the node 4 right in the infinite planar binary tree. The fourth row of A065625. Inverse of A065632.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A065637 Permutation of N induced by rotating the node 7 right in the infinite planar binary tree. The seventh row of A065625. Inverse of A065638.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A065639 Permutation of N induced by rotating the node 8 right in the infinite planar binary tree. The eighth row of A065625. Inverse of A065640.

Views

Author

Keywords

Links

Crossrefs

Programs