A381457 Integers encoding the recursive structure of a bitonic sorter network of n elements in their binary expansion.

0, 2, 5, 2762, 22325, 175338, 1405781, 187796017958058, 12026023042822997, 768764969792360106, 49208135664973067605, 3148398007269257431722, 201504853864147844281685, 12895366188400224861219498, 825310989999256684769531221

Offset: 1

Author

Darío Clavijo, Mar 13 2025

Keywords

• nonn
• base

Comments

These integers represent the control logic or network topology of a bitonic sorter, a parallel sorting algorithm. For n = 2^k, their binary expansions mirror the sorter's recursive, fractal-like stages: each level splits into two smaller sorters (n/2), followed by a merging step. This creates a self-similar pattern where the binary bits 'track' the hierarchical stages of the algorithm.

A bitonic sorting network for n = 2^k elements requires (n/2)*(log_2(n))*(log_2(n) + 1) comparators (Batcher, 1968). This sequence extends the construction to arbitrary n by padding to the next power of 2 and pruning redundant comparators. The validity of this generalization as a sorting network remains conjectural; proofs are sought.

a(n) is constructed in most significant bit to less significant bit order.

Also, for n=2^k the comparator network has n columns and A000217(k) rows and a(n) has A001788(n) bits set which is exactly half of the bit size of a(n).

The parity of a(n) is the same parity of n for n > 1.

For n >= 4, a(n) is composed of repeating patterns of bits, take for instance a(11) = 10101010101_11001100110_10101010101_11110000111_11001100110_10101010101_2 = 49208135664973067605. This shows the self-similarity pattern.

Examples

			 n | k  | i                   | Comparator network (1 = \ and 0 = /). | a(n)
---+----+---------------------+---------------------------------------+----------------
 2 | 2  | 10                  | \/                                    | 2
---+----+---------------------+---------------------------------------+----------------
 4 | 2  | 1010                | \/ \/                                 | 2762
   | 4  | 1100                | \   /                                 |
   | 4  | 1010                | \/ \/                                 |
---+----+---------------------+---------------------------------------+----------------
 8 | 2  | 1010 1010           | \/ \/ \/ \/                           | 187796017958058
   | 4  | 1100 1100           | \   / \   /                           |
   | 4  | 1010 1010           | \/ \/ \/ \/                           |
   | 8  | 1111 0000           | \         /                           |
   | 8  | 1100 1100           | \   / \   /                           |
   | 8  | 1010 1010           | \/ \/ \/ \/
For n = 5 the network is similar to the network for n = 4 plus a column of ones, which is also a network contained in the network for n = 8.
 5 | 2  | 1010 1              | \/ \/ \                               | 22325
   | 4  | 1100 1              | \   / \                               |
   | 4  | 1010 1              | \/ \/ \                               |
		

Links

• K. E. Batcher, Sorting networks and their applications, AFIPS '68 (Spring): Proceedings of the April 30--May 2, 1968, Spring Joint Computer Conference, Pages 307 - 314.
• Wikipedia, Bitonic sorter

Crossrefs

Cf. A000217, A001788.

Programs

Python

def a(n):
    e, k = 0, 2
    while k <= n:
        j = k >> 1
        while j > 0:
            for i in range(n):
                e = (e << 1) | ((i & j) == 0)
            j >>= 1
        k <<= 1
    return e
print([a(n) for n in range(1,16)])