login
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

%I #71 Jul 27 2020 19:53:17

%S 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,

%T 23,26,27,29,31,16,17,33,19,34,35,37,23,36,37,41,39,42,43,45,31,40,41,

%U 49,43,50,51,53,47,52,53,57,55,58,59,61,63,32,33,65,35,66,67,69

%N 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.

%C 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.]

%C 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.

%C 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.

%H Philippe Beaudoin, <a href="/A241816/b241816.txt">Table of n, a(n) for n = 0..9999</a>

%F 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

%e If n = 5 = 101_2 then a(n) = 011_2 = 3.

%e If n = 8 = 1000_2 then a(8) = 0100_2 = 4.

%o (Python)

%o def bitswap(n):

%o ..# Find first bit = 0.

%o ..m = n

%o ..i = 0

%o ..while (m > 0):

%o ....if m % 2 == 0:

%o ......break

%o ....m = m >> 1

%o ....i = i + 1

%o ..if m == 0:

%o .....return n

%o ..# Find first bit = 1 following that 0.

%o ..while (m > 0):

%o ....if m % 2 == 1:

%o ......break

%o ....m = m >> 1

%o ....i = i + 1

%o ..# Swap

%o ..return n & ~(1 << i) | (1 << (i-1))

%o (Haskell)

%o a241816 n = f (a030308_row n) [] where

%o f [] _ = n

%o f (0 : 1 : us) vs = foldr (\b y -> 2 * y + b) 0 $

%o reverse vs ++ 1 : 0 : us

%o f (u : us) vs = f us (u : vs)

%o -- _Reinhard Zumkeller_, Sep 03 2014

%o (Python)

%o def A241816(n):

%o ....s = bin(n)[2:]

%o ....for i in range(len(s)-2,-1,-1):

%o ........if s[i:i+2] == '10':

%o ............return int(s[:i]+'01'+s[i+2:],2)

%o ....else:

%o ........return n

%o # _Chai Wah Wu_, Sep 05 2014

%o (Scheme, with memoization-macro definec)

%o (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))))

%o ;; _Antti Karttunen_, Feb 21 2015

%Y Cf. A055941, A030101, A030308, A007088, A246591, A246592, A246593, A246594.

%Y Complement is A246590.

%K nonn,base

%O 0,4

%A _Philippe Beaudoin_, Aug 19 2014

%E Definition clarified by _Chai Wah Wu_, Sep 05 2014