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.

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

Offset: 0

Author

Philippe Beaudoin, Aug 19 2014

Keywords

• nonn
• base

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.

Examples

			If n = 5 = 101_2 then a(n) = 011_2 = 3.
If n = 8 = 1000_2 then a(8) = 0100_2 = 4.
		

Links

• Philippe Beaudoin, Table of n, a(n) for n = 0..9999

Crossrefs

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

Complement is A246590.

Programs

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

Mathematica

A241816[n_] := FromDigits[StringReverse[StringReplace[StringReverse[IntegerString[n, 2]], "01" -> "10", 1]], 2];
Array[A241816, 100, 0] (* Paolo Xausa, Mar 07 2025 *)

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))

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

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

Extensions

Definition clarified by Chai Wah Wu, Sep 05 2014