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.
%I A381457 #51 Apr 01 2025 18:12:49 %S A381457 0,2,5,2762,22325,175338,1405781,187796017958058,12026023042822997, %T A381457 768764969792360106,49208135664973067605,3148398007269257431722, %U A381457 201504853864147844281685,12895366188400224861219498,825310989999256684769531221 %N A381457 Integers encoding the recursive structure of a bitonic sorter network of n elements in their binary expansion. %C A381457 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. %C A381457 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. %C A381457 a(n) is constructed in most significant bit to less significant bit order. %C A381457 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). %C A381457 The parity of a(n) is the same parity of n for n > 1. %C A381457 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. %H A381457 K. E. Batcher, <a href="https://doi.org/10.1145/1468075.1468121">Sorting networks and their applications</a>, AFIPS '68 (Spring): Proceedings of the April 30--May 2, 1968, Spring Joint Computer Conference, Pages 307 - 314. %H A381457 Wikipedia, <a href="https://en.wikipedia.org/wiki/Bitonic_sorter">Bitonic sorter</a> %e A381457 n | k | i | Comparator network (1 = \ and 0 = /). | a(n) %e A381457 ---+----+---------------------+---------------------------------------+---------------- %e A381457 2 | 2 | 10 | \/ | 2 %e A381457 ---+----+---------------------+---------------------------------------+---------------- %e A381457 4 | 2 | 1010 | \/ \/ | 2762 %e A381457 | 4 | 1100 | \ / | %e A381457 | 4 | 1010 | \/ \/ | %e A381457 ---+----+---------------------+---------------------------------------+---------------- %e A381457 8 | 2 | 1010 1010 | \/ \/ \/ \/ | 187796017958058 %e A381457 | 4 | 1100 1100 | \ / \ / | %e A381457 | 4 | 1010 1010 | \/ \/ \/ \/ | %e A381457 | 8 | 1111 0000 | \ / | %e A381457 | 8 | 1100 1100 | \ / \ / | %e A381457 | 8 | 1010 1010 | \/ \/ \/ \/ %e A381457 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. %e A381457 5 | 2 | 1010 1 | \/ \/ \ | 22325 %e A381457 | 4 | 1100 1 | \ / \ | %e A381457 | 4 | 1010 1 | \/ \/ \ | %o A381457 (Python) %o A381457 def a(n): %o A381457 e, k = 0, 2 %o A381457 while k <= n: %o A381457 j = k >> 1 %o A381457 while j > 0: %o A381457 for i in range(n): %o A381457 e = (e << 1) | ((i & j) == 0) %o A381457 j >>= 1 %o A381457 k <<= 1 %o A381457 return e %o A381457 print([a(n) for n in range(1,16)]) %Y A381457 Cf. A000217, A001788. %K A381457 nonn,base %O A381457 1,2 %A A381457 _Darío Clavijo_, Mar 13 2025