login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 107
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

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))) [where A is an abbreviation for A059893 itself]. - Antti Karttunen, Oct 28 2001

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)

LINKS

T. D. Noe and 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

FORMULA

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

EXAMPLE

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)

MAPLE

# 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

MATHEMATICA

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

PROG

(PARI) { for (n=1, 1023, a=1; b=n; while (b>1, a=2*a + 2*frac(b/2); b=floor(b/2); ); write("b059893.txt", n, " ", a); ) } \\ Harry J. Smith, Jun 30 2009

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

(Haskell)

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

(R)

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

(R)

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

(Python)

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

CROSSREFS

{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).

Sequence in context: A139708 A333776 A305410 * A331274 A269365 A269366

Adjacent sequences: A059890 A059891 A059892 * A059894 A059895 A059896

KEYWORD

easy,nonn,base,nice,look

AUTHOR

Marc LeBrun, Feb 06 2001

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 5 14:52 EST 2023. Contains 360086 sequences. (Running on oeis4.)