A220001 Benes network size for permutations of n.

0, 1, 3, 6, 8, 12, 15, 20, 22, 26, 30, 36, 39, 44, 49, 56, 58, 62, 66, 72, 76, 82, 88, 96, 99, 104, 109, 116, 121, 128, 135, 144, 146, 150, 154, 160, 164, 170, 176, 184, 188, 194, 200, 208, 214, 222, 230, 240, 243, 248, 253, 260, 265, 272, 279, 288, 293, 300

Offset

1,3

Comments

a(n) is the number of 2 X 2 direct/crisscross switches required to construct an n X n crossbar for any permutation.

References

Hsien-Kuei Hwang, S Janson, TH Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint, 2016; http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf. Also Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585

Links

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

Chihming Chang and Rami Melhem, Arbitrary Size Benes Networks

Formula

a(n) = 2*floor(n/2) + a(floor(n/2)) + a(ceiling(n/2)) for n > 2 and a(1)=0 and a(2)=1.

Example

n=1 does not need any switches, n=2 needs just one 2 X 2 switch, n=3 needs three switches (1 X 2, 2 X 3, 1 X 2).

Crossrefs

Sequence in context: A185597 A082873 A182727 * A310138 A310139 A350619

Adjacent sequences: A219998 A219999 A220000 * A220002 A220003 A220004

Keyword

nonn

Author

Leonid Broukhis, Dec 03 2012

Status

approved