cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

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.

Original entry on oeis.org

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

Views

Author

Philippe Beaudoin, Aug 19 2014

Keywords

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

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

A246593 a(n)=n for n <= 2; for n >= 3, a(n) = largest number that can be obtained by swapping two bits in the binary expansion of n.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 6, 7, 8, 12, 12, 14, 12, 14, 14, 15, 16, 24, 24, 26, 24, 28, 28, 30, 24, 28, 28, 30, 28, 30, 30, 31, 32, 48, 48, 50, 48, 52, 52, 54, 48, 56, 56, 58, 56, 60, 60, 62, 48, 56, 56, 58, 56, 60, 60, 62, 56, 60, 60, 62, 60, 62, 62, 63, 64, 96, 96
Offset: 0

Views

Author

N. J. A. Sloane, Sep 03 2014

Keywords

Comments

In both this sequence and A246594 you are not allowed to touch any of the invisible 0's before the leading 1.
Swap first 0 with last 1 in the binary expansion of n or return n if no such swap is possible. - Chai Wah Wu, Sep 08 2014

Examples

			If n = 17 = 10001_2 then a(17) = 11000_2 = 24.

Links

Crossrefs

Cf. A241816, A246591, A246592, A246594.

Programs

  • Python
    from itertools import combinations
def A246593(n):
    if n <= 1:
        return n
    else:
        s, y = bin(n)[2:], n
        for i in combinations(range(len(s)),2):
            s2 = int(s[:i[0]]+s[i[1]]+s[i[0]+1:i[1]]+s[i[0]]+s[i[1]+1:],2)
            if s2 > y:
                y = s2
        return y
# Chai Wah Wu, Sep 05 2014
  • Python
    # implement algorithm in comment
def A246593(n):
    s = bin(n)[2:]
    s2 = s.rstrip('0')
    s3 = s2.lstrip('1')
    return(int(s2[:-len(s3)]+'1'+s3[1:-1]+'0'+s[len(s2):],2) if (len(s3) > 0 and n > 1) else n)
# Chai Wah Wu, Sep 08 2014

Extensions

Corrected definition and more terms from Alois P. Heinz, Sep 04 2014

A246591 Smallest number that can be obtained by swapping 2 bits in the binary expansion of n.

Original entry on oeis.org

0, 1, 1, 3, 1, 3, 3, 7, 1, 3, 3, 7, 5, 7, 7, 15, 1, 3, 3, 7, 5, 7, 7, 15, 9, 11, 11, 15, 13, 15, 15, 31, 1, 3, 3, 7, 5, 7, 7, 15, 9, 11, 11, 15, 13, 15, 15, 31, 17, 19, 19, 23, 21, 23, 23, 31, 25, 27, 27, 31, 29, 31, 31, 63, 1, 3, 3, 7, 5, 7, 7, 15, 9, 11, 11
Offset: 0

Views

Author

N. J. A. Sloane, Sep 03 2014

Keywords

Comments

Swap the first 1 with the last 0 in the binary expansion of n.

Examples

			If n = 12 = 1100_2 then a(12) = 0101_2 = 5.

Links

Crossrefs

Cf. A241816, A246592, A246593, A246594.

Programs

  • Python
    from itertools import combinations
def A246591(n):
    if n <= 1:
        return n
    else:
        s = bin(n)[2:]
        l = len(s)
        y = 2**l-1
        for i in combinations(range(l), 2):
            s2 = int(s[:i[0]]+s[i[1]]+s[i[0]+1:i[1]]+s[i[0]]+s[i[1]+1:], 2)
            if s2 < y:
                y = s2
        return y
# Chai Wah Wu, Sep 05 2014
  • Python
    def A246591(n):
    s = bin(n)[2:]
    s2 = s.rstrip('1')
    return(int(s2[1:-1]+'1'+s[len(s2):], 2) if (len(s2) > 0 and n > 1) else n)
# Chai Wah Wu, Sep 08 2014

Extensions

More terms from Alois P. Heinz, Sep 03 2014

A246592 Smallest number that can be obtained by swapping 2 adjacent bits in the binary expansion of n.

Original entry on oeis.org

0, 1, 1, 3, 2, 3, 5, 7, 4, 5, 6, 7, 10, 11, 13, 15, 8, 9, 10, 11, 12, 13, 14, 15, 20, 21, 22, 23, 26, 27, 29, 31, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 40, 41, 42, 43, 44, 45, 46, 47, 52, 53, 54, 55, 58, 59, 61, 63, 32, 33, 34, 35, 36
Offset: 0

Views

Author

N. J. A. Sloane, Sep 03 2014

Keywords

Comments

Scanning from the left, find first occurrence of '10' in binary expansion and replace with '01' and return decimal representation or return n if no such swap exists. - Chai Wah Wu, Sep 06 2014

Examples

			If n = 9 = 1001_2 then a(9) = 0101_2 = 5.

Links

Crossrefs

Cf. A241816, A246591, A246593, A246594.

Programs

  • Mathematica
    A246592[n_] := FromDigits[StringReplace[IntegerString[n, 2], "10" -> "01", 1], 2];
Array[A246592, 100, 0] (* Paolo Xausa, Mar 07 2025 *)
  • Python
    def A246592(n):
    s = bin(n)[2:]
    for i in range(len(s)-1):
        if s[i:i+2] == '10':
            return int(s[:i]+'01'+s[i+2:], 2)
    else:
        return n # Chai Wah Wu, Sep 06 2014

Extensions

More terms from Alois P. Heinz, Sep 03 2014
Showing 1-4 of 4 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.