cp's OEIS Frontend

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.

%I A059893 #111 Dec 08 2024 12:26:05
%S A059893 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,
%T A059893 29,19,27,23,31,32,48,40,56,36,52,44,60,34,50,42,58,38,54,46,62,33,49,
%U A059893 41,57,37,53,45,61,35,51,43,59,39,55,47,63,64,96,80,112,72,104,88,120
%N 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.
%C A059893 A self-inverse permutation of the natural numbers.
%C A059893 a(n)=n if and only if A081242(n) is a palindrome. - _Clark Kimberling_, Mar 12 2003
%C A059893 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
%C A059893 From _Antti Karttunen_, Oct 28 2001: (Start)
%C A059893 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:
%C A059893    A065260(n) = a(A057115(a(n))),
%C A059893    A065266(n) = a(A065264(a(n))),
%C A059893    A065272(n) = a(A065270(a(n))),
%C A059893    A065278(n) = a(A065276(a(n))),
%C A059893    A065284(n) = a(A065282(a(n))),
%C A059893    A065290(n) = a(A065288(a(n))). (End)
%C A059893 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
%C A059893 From _Ed Pegg Jr_, Sep 09 2015: (Start)
%C A059893 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.
%C A059893 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).
%C A059893 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).
%C A059893 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)
%H A059893 Alois P. Heinz, <a href="/A059893/b059893.txt">Table of n, a(n) for n = 1..8191</a> (first 1023 terms from T. D. Noe)
%H A059893 Bruce Bates, Martin Bunder, and Keith Tognetti, <a href="http://dx.doi.org/10.1016/j.ejc.2007.10.005">Locating terms in the Stern-Brocot tree</a>, European Journal of Combinatorics 31.3 (2010): 1020-1033.
%H A059893 Joe Buhler and R. L. Graham, <a href="http://www.cecm.sfu.ca/organics/papers/buhler/index.html">Juggling Drops and Descents</a>, Amer. Math. Monthly, 101, (no. 6) 1994, 507-519.
%H A059893 Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang, <a href="https://arxiv.org/abs/2012.04625">Finding structure in sequences of real numbers via graph theory: a problem list</a>, arXiv:2012.04625, 2020-2021.
%H A059893 Wikipedia, <a href="https://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree">Calkin-Wilf Tree</a>.
%H A059893 Wikipedia, <a href="https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree">Stern-Brocot tree</a>.
%H A059893 <a href="/index/St#Stern">Index entries for sequences related to Stern's sequences</a>
%H A059893 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A059893 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
%e A059893 a(11) = a(1011) = 1110 = 14.
%e A059893 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
%e A059893 From _Philippe Deléham_, Jun 02 2015: (Start)
%e A059893 This sequence regarded as a triangle with rows of lengths 1, 2, 4, 8, 16, ...:
%e A059893    1;
%e A059893    2,  3;
%e A059893    4,  6,  5,  7;
%e A059893    8, 12, 10, 14,  9,  13,  11,  15;
%e A059893   16, 24, 20, 28, 18,  26,  22,  30,  17,  25,  21,  29,  19,  27,  23,  31;
%e A059893   32, 48, 40, 56, 36,  52,  44, ...
%e A059893 Row sums = A010036. (End)
%p A059893 # Implements Bottomley's formula
%p A059893 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;
%p A059893 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;
%p A059893 # second Maple program:
%p A059893 a:= proc(n) local i, m, r; m, r:= n, 0;
%p A059893       for i from 0 while m>1 do r:= 2*r +irem(m,2,'m') od;
%p A059893       r +2^i
%p A059893     end:
%p A059893 seq(a(n), n=1..100);  # _Alois P. Heinz_, Feb 28 2015
%t A059893 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_ *)
%t A059893 ro[n_]:=Module[{idn=IntegerDigits[n,2]},FromDigits[Join[{First[idn]}, Reverse[ Rest[idn]]],2]]; Array[ro,80] (* _Harvey P. Dale_, Oct 24 2012 *)
%o A059893 (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
%o A059893 (Haskell)
%o A059893 a059893 = foldl (\v b -> v * 2 + b) 1 . init . a030308_row
%o A059893 -- _Reinhard Zumkeller_, May 01 2013
%o A059893 (Scheme, with memoization-macro definec)
%o A059893 (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)))))
%o A059893 ;; _Antti Karttunen_, May 16 2015
%o A059893 (R)
%o A059893 maxrow <- 6 # by choice
%o A059893 a <- 1
%o A059893 for(m in 0:maxrow) for(k in 0:(2^m-1)) {
%o A059893   a[2^(m+1)+    k] <- 2*a[2^m+k]
%o A059893   a[2^(m+1)+2^m+k] <- 2*a[2^m+k] + 1
%o A059893 }
%o A059893 a
%o A059893 # _Yosu Yurramendi_, Mar 20 2017
%o A059893 (R)
%o A059893 maxblock <- 7 # by choice
%o A059893 a <- 1
%o A059893 for(n in 2:2^maxblock){
%o A059893   ones <- which(as.integer(intToBits(n)) == 1)
%o A059893   nbit <- as.integer(intToBits(n))[1:tail(ones, n = 1)]
%o A059893   anbit <- nbit
%o A059893   anbit[1:(length(anbit) - 1)] <- anbit[rev(1:(length(anbit)-1))]
%o A059893   a <- c(a, sum(anbit*2^(0:(length(anbit) - 1))))
%o A059893 }
%o A059893 a
%o A059893 # _Yosu Yurramendi_, Apr 25 2021
%o A059893 (Python)
%o A059893 def a(n): return int('1' + bin(n)[3:][::-1], 2)
%o A059893 print([a(n) for n in range(1, 101)]) # _Indranil Ghosh_, Mar 21 2017
%Y A059893 {A000027, A054429, A059893, A059894} form a 4-group.
%Y A059893 The set of permutations {A059893, A080541, A080542} generates an infinite dihedral group.
%Y A059893 Cf. A000079, A000523, A007931, A030308.
%Y A059893 In other bases: A351702 (balanced ternary), A343150 (Zeckendorf), A343152 (lazy Fibonacci).
%K A059893 easy,nonn,base,nice,look
%O A059893 1,2
%A A059893 _Marc LeBrun_, Feb 06 2001