cp's OEIS Frontend

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.

%I A241816 #78 Mar 22 2025 12:55:31
%S A241816 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 A241816 23,26,27,29,31,16,17,33,19,34,35,37,23,36,37,41,39,42,43,45,31,40,41,
%U A241816 49,43,50,51,53,47,52,53,57,55,58,59,61,63,32,33,65,35,66,67,69
%N 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.
%C A241816 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 A241816 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 A241816 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 A241816 Philippe Beaudoin, <a href="/A241816/b241816.txt">Table of n, a(n) for n = 0..9999</a>
%F A241816 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 A241816 If n = 5 = 101_2 then a(n) = 011_2 = 3.
%e A241816 If n = 8 = 1000_2 then a(8) = 0100_2 = 4.
%t A241816 A241816[n_] := FromDigits[StringReverse[StringReplace[StringReverse[IntegerString[n, 2]], "01" -> "10", 1]], 2];
%t A241816 Array[A241816, 100, 0] (* _Paolo Xausa_, Mar 07 2025 *)
%o A241816 (Python)
%o A241816 def bitswap(n):
%o A241816   # Find first bit = 0.
%o A241816   m = n
%o A241816   i = 0
%o A241816   while (m > 0):
%o A241816     if m % 2 == 0:
%o A241816       break
%o A241816     m = m >> 1
%o A241816     i = i + 1
%o A241816   if m == 0:
%o A241816      return n
%o A241816   # Find first bit = 1 following that 0.
%o A241816   while (m > 0):
%o A241816     if m % 2 == 1:
%o A241816       break
%o A241816     m = m >> 1
%o A241816     i = i + 1
%o A241816   # Swap
%o A241816   return n & ~(1 << i) | (1 << (i-1))
%o A241816 (Haskell)
%o A241816 a241816 n = f (a030308_row n) [] where
%o A241816    f [] _ = n
%o A241816    f (0 : 1 : us) vs = foldr (\b y -> 2 * y + b) 0 $
%o A241816                              reverse vs ++ 1 : 0 : us
%o A241816    f (u : us) vs     = f us (u : vs)
%o A241816 -- _Reinhard Zumkeller_, Sep 03 2014
%o A241816 (Python)
%o A241816 def A241816(n):
%o A241816     s = bin(n)[2:]
%o A241816     for i in range(len(s)-2, -1, -1):
%o A241816         if s[i:i+2] == '10':
%o A241816             return int(s[:i]+'01'+s[i+2:], 2)
%o A241816     else:
%o A241816         return n
%o A241816 # _Chai Wah Wu_, Sep 05 2014
%o A241816 (Scheme)
%o A241816 ;; With memoization-macro definec.
%o A241816 (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 A241816 ;; _Antti Karttunen_, Feb 21 2015
%Y A241816 Cf. A055941, A030101, A030308, A007088, A246591, A246592, A246593, A246594.
%Y A241816 Complement is A246590.
%K A241816 nonn,base
%O A241816 0,4
%A A241816 _Philippe Beaudoin_, Aug 19 2014
%E A241816 Definition clarified by _Chai Wah Wu_, Sep 05 2014