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.
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
Examples
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)
Links
- 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
Crossrefs
Programs
-
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
-
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 *)
-
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
-
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 -
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
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
Comments