%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