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

Author

Leonid Broukhis, Dec 03 2012

Keywords

• nonn

Comments

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

Examples

			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).
		

Links

• Paolo Xausa, Table of n, a(n) for n = 1..10000
• Chihming Chang and Rami Melhem, Arbitrary Size Benes Networks
• 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; 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

Programs

Mathematica

A220001[n_] := A220001[n] = If[n < 3, n - 1, 2*Floor[n/2] + A220001[Floor[n/2]] + A220001[Ceiling[n/2]]]; Array[A220001, 100] (* Paolo Xausa, Aug 03 2024 *)

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.