A065260 -id:A065260 - cp's OEIS frontend

A065259 A057114 conjugated with A059893, inverse of A065260.

3, 1, 7, 2, 11, 5, 15, 4, 19, 9, 23, 6, 27, 13, 31, 8, 35, 17, 39, 10, 43, 21, 47, 12, 51, 25, 55, 14, 59, 29, 63, 16, 67, 33, 71, 18, 75, 37, 79, 20, 83, 41, 87, 22, 91, 45, 95, 24, 99, 49, 103, 26, 107, 53, 111, 28, 115, 57, 119, 30, 123, 61, 127, 32, 131, 65, 135, 34, 139

Offset: 1

Antti Karttunen, Oct 28 2001

			G.f. = 3*x + x^2 + 7*x^3 + 2*x^4 + 11*x^5 + 5*x^6 + 15*x^7 + 4*x^8 + ...

Colin Barker, Table of n, a(n) for n = 1..1000
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).

Vec(x*(3+x+7*x^2+2*x^3+5*x^4+3*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, 2*n+1, n%4, n-1, n/2)}; /* Michael Somos, Nov 06 2016 */

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

A065261 The siteswap sequence (the deltas p[i]-i, i in ]-inf,+inf[, folded from Z to N, mapping 0->1, 1->2, -1->3, 2->4, -2->5, etc.) for A065260.

Original entry on oeis.org

1, 1, 1, 2, 5, 3, 2, 4, 9, 5, 3, 6, 13, 7, 4, 8, 17, 9, 5, 10, 21, 11, 6, 12, 25, 13, 7, 14, 29, 15, 8, 16, 33, 17, 9, 18, 37, 19, 10, 20, 41, 21, 11, 22, 45, 23, 12, 24, 49, 25, 13, 26, 53, 27, 14, 28, 57, 29, 15, 30, 61, 31, 16, 32, 65, 33, 17, 34, 69, 35, 18, 36, 73, 37, 19, 38

Offset: 1

Antti Karttunen, Oct 28 2001

nonn

The bisection giving the positive half of Z is A000027 and the nonpositive half is A065262. Cf. also A065173.

a(2n+2) = n+1, a(4n+1) = 4n+1, a(4n+3) = n+1. - Ralf Stephan, Jun 10 2005
Empirical g.f.: x*(x^5+3*x^4+2*x^3+x^2+x+1) / ((x-1)^2*(x+1)^2*(x^2+1)^2). [Colin Barker, Feb 18 2013]
From Luce ETIENNE, Feb 01 2017 : (Start)
a(n) = 2*a(n-4)-a(n-8).
a(n) = (9*n+1-(n+1)*(-1)^n+(3*n-1)*((-1)^((2*n-1+(-1)^n)/4)-(-1)^((2*n+1-(-1)^n)/4)))/16.
a(n) = (9*n+1-(n+1)*cos(n*Pi)+2*(3*n-1)*sin(n*Pi/2))/16. (End)

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

A057115 Order-preserving permutation of the rational numbers (x -> x-1); positions in Stern-Brocot tree.

Original entry on oeis.org

2, 4, 1, 8, 9, 5, 3, 16, 17, 18, 19, 10, 11, 6, 7, 32, 33, 34, 35, 36, 37, 38, 39, 20, 21, 22, 23, 12, 13, 14, 15, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 40, 41, 42, 43, 44, 45, 46, 47, 24, 25, 26, 27, 28, 29, 30, 31, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150

Offset: 1

Antti Karttunen, Aug 09 2000

nonn

Inverse permutation: A057114.
When conjugated with A059893, one gets A065260, a valid siteswap permutation.
The first row of A065626, i.e. a(n) = RotateNodeLeft(1, n).

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

a(n) = frac2position_in_whole_SB_tree(sbtree_perm_1_1_left(SternBrocotTreeNum(n)/SternBrocotTreeDen(n)))

A065171 Permutation of Z, folded to N, corresponding to the site swap pattern ...26120123456... which ascends infinitely after t=0.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Oct 19 2001

This permutation consists of one fixed point (at 0, mapped here to 1) and an infinite number of infinite cycles.

			G.f. = x + 4*x^2 + 2*x^3 + 8*x^4 + 3*x^5 + 12*x^6 + 6*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).

Inverse permutation: A065172. A065173 gives the deltas p(t)-t, i.e., the associated site swap sequence. Cf. also A065167, A065174, A065260.

[seq(Z2N(InfRisingSS(N2Z(n))), n=1..120)]; InfRisingSS := z -> `if`((z < 0),`if`((0 = (z mod 2)),z/2,-z),2*z);
N2Z := n -> ((-1)^n)*floor(n/2); Z2N := z -> 2*abs(z)+`if`((z < 1),1,0);

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

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

a(2*k+2) = 4*k+4, a(4*k+1) = 2*k+1, a(4*k+3) = 4*k+2. - Ralf Stephan, Jun 10 2005
G.f.: x*(2*x^6+4*x^5+x^4+8*x^3+2*x^2+4*x+1) / ((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

cp's OEIS Frontend

A065259 A057114 conjugated with A059893, inverse of A065260.

Views

Author

Keywords

Examples

Links

Programs

PARI

PARI

Formula

A065261 The siteswap sequence (the deltas p[i]-i, i in ]-inf,+inf[, folded from Z to N, mapping 0->1, 1->2, -1->3, 2->4, -2->5, etc.) for A065260.

Views

Author

Keywords

Crossrefs

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

A057115 Order-preserving permutation of the rational numbers (x -> x-1); positions in Stern-Brocot tree.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A065171 Permutation of Z, folded to N, corresponding to the site swap pattern ...26120123456... which ascends infinitely after t=0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

PARI

Formula