The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A241816 a(n) is the largest number smaller than n that can be obtained by swapping two adjacent bits in n, or n if no such number exists. 8
 0, 1, 1, 3, 2, 3, 5, 7, 4, 5, 9, 7, 10, 11, 13, 15, 8, 9, 17, 11, 18, 19, 21, 15, 20, 21, 25, 23, 26, 27, 29, 31, 16, 17, 33, 19, 34, 35, 37, 23, 36, 37, 41, 39, 42, 43, 45, 31, 40, 41, 49, 43, 50, 51, 53, 47, 52, 53, 57, 55, 58, 59, 61, 63, 32, 33, 65, 35, 66, 67, 69 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,4 COMMENTS Equivalently, a(n) is obtained by swapping the first pair of adjacent bits equal to "10", if such a pair exists. [Here the first pair means the first pair from the right, the least significant end of binary expansion. Comment clarified by Antti Karttunen, Feb 20 2015.] The fixed point of a(n) is equal to 2^k - 1, where k = A000120(n). In other words, applying a(n) repeatedly packs all the bits to the right. a(n) is related to the "bubble sort" algorithm. If an array of elements from two classes is encoded in a binary number, a(n) is the first intermediate result that will be obtained when starting a bubble sort from n. LINKS Philippe Beaudoin, Table of n, a(n) for n = 0..9999 FORMULA a(0) = 0; a(2n+1) = 1+2*a(n), a(4n) = 2*a(2n), a(4n+2) = 4n+1. - Antti Karttunen, Feb 21 2015 EXAMPLE If n = 5 = 101_2 then a(n) = 011_2 = 3. If n = 8 = 1000_2 then a(8) = 0100_2 = 4. PROG (Python) def bitswap(n): ..# Find first bit = 0. ..m = n ..i = 0 ..while (m > 0): ....if m % 2 == 0: ......break ....m = m >> 1 ....i = i + 1 ..if m == 0: .....return n ..# Find first bit = 1 following that 0. ..while (m > 0): ....if m % 2 == 1: ......break ....m = m >> 1 ....i = i + 1 ..# Swap ..return n & ~(1 << i) | (1 << (i-1)) (Haskell) a241816 n = f (a030308_row n) [] where    f [] _ = n    f (0 : 1 : us) vs = foldr (\b y -> 2 * y + b) 0 \$                              reverse vs ++ 1 : 0 : us    f (u : us) vs     = f us (u : vs) -- Reinhard Zumkeller, Sep 03 2014 (Python) def A241816(n): ....s = bin(n)[2:] ....for i in range(len(s)-2, -1, -1): ........if s[i:i+2] == '10': ............return int(s[:i]+'01'+s[i+2:], 2) ....else: ........return n # Chai Wah Wu, Sep 05 2014 (Scheme, with memoization-macro definec) (definec (A241816 n) (cond ((zero? n) n) ((odd? n) (+ 1 (* 2 (A241816 (/ (- n 1) 2))))) ((zero? (modulo n 4)) (* 2 (A241816 (/ n 2)))) (else (- n 1)))) ;; Antti Karttunen, Feb 21 2015 CROSSREFS Cf. A055941, A030101, A030308, A007088, A246591, A246592, A246593, A246594. Complement is A246590. Sequence in context: A050060 A247829 A246592 * A243109 A206012 A211940 Adjacent sequences:  A241813 A241814 A241815 * A241817 A241818 A241819 KEYWORD nonn,base AUTHOR Philippe Beaudoin, Aug 19 2014 EXTENSIONS Definition clarified by Chai Wah Wu, Sep 05 2014 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 25 05:43 EDT 2020. Contains 337334 sequences. (Running on oeis4.)