A380145 The binary expansion of a(n) is an initial 1 bit then tracks where the swaps occur in the exchange sort algorithm sorting the binary expansion of n into decreasing order.

1, 2, 2, 8, 9, 8, 8, 64, 66, 68, 69, 64, 65, 64, 64, 1024, 1032, 1040, 1042, 1056, 1058, 1060, 1061, 1024, 1026, 1028, 1029, 1024, 1025, 1024, 1024, 32768, 32832, 32896, 32904, 33024, 33032, 33040, 33042, 33280, 33288, 33296, 33298, 33312, 33314, 33316, 33317

Offset

1,2

Comments

The binary expansion of n is taken as a vector B, most significant bit first.

The exchange sort performs a compare-and-swap operation between elements at positions i,j running i = 1 to L-1 and on each i successively j = i+1 to L, where L = A070939(n) is the vector length and i=1 if the first vector element.

Each swap is encoded as a 1 bit in a(n), and no-swap as a 0 bit.

The most significant bit of n is always 1 so never swaps and the first L-1 bits encoded are always 0.

If the bits of n are already in decreasing order (A023758) then there are no swaps at all and a(n) = 2^(L*(L-1)/2) = A006125(L).

Links

Table of n, a(n) for n=1..47.

Example

n= 22 = 10110_2 is a bit vector B = [1,0,1,1,0], and the swaps performed are then
   i | j | B[i] | B[j] | Encoding
  ---+---+------+------+----------
   - | - |  -   |  -   |   1
   1 | 2 |  1   |  0   |   0
   1 | 3 |  1   |  1   |   0
   1 | 4 |  1   |  1   |   0
   1 | 5 |  1   |  0   |   0
   2 | 3 |  0   |  1   |   1
   2 | 4 |  1   |  1   |   0
   2 | 5 |  1   |  0   |   0
   3 | 4 |  0   |  1   |   1
   3 | 5 |  1   |  0   |   0
   4 | 5 |  0   |  0   |   0
The resulting sorted B vector is [1,1,1,0,0] and the encoded swaps performed are
  a(22) = binary 1 0000 100 10 0 = 1060.

Prog

(Python)
def a(n):
    c, B, lb = 2, list(map(int, bin(n)[2:])), n.bit_length()
    for i in range(lb):
        for j in range(i+1, lb):
            if B[i] < B[j]:
                B[i], B[j] = B[j], B[i]
                c |=1
            c <<= 1
    return c >> 1
print([a(n) for n in range(1, 48)])

Crossrefs

Cf. A000079, A000217, A006125, A023758, A070939.

Sequence in context: A244676 A010584 A131659 * A137726 A121098 A121094

Adjacent sequences: A380142 A380143 A380144 * A380146 A380147 A380148

Keyword

nonn,base,new

Author

Darío Clavijo, Jan 13 2025

Status

approved