login
This site is supported by donations 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. 57
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-Brocat 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-Brocat 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-Brocat 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-Brocat 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.

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

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. - Philippe Deléham, Jun 02 2015

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

(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

(Python)

def a(n): return (int(bin(n)[2:][::-1], 2) - 1)/2

def msb(n): return n if n<3 else msb(n/2)*2

print [a(n) + msb(n) for n in xrange(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.

Sequence in context: A104464 A139706 A139708 * A269365 A269366 A275376

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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 24 07:19 EDT 2017. Contains 288697 sequences.