|
%I #22 Aug 03 2024 17:08:19
%S 0,1,3,6,8,12,15,20,22,26,30,36,39,44,49,56,58,62,66,72,76,82,88,96,
%T 99,104,109,116,121,128,135,144,146,150,154,160,164,170,176,184,188,
%U 194,200,208,214,222,230,240,243,248,253,260,265,272,279,288,293,300
%N Benes network size for permutations of n.
%C a(n) is the number of 2 X 2 direct/crisscross switches required to construct an n X n crossbar for any permutation.
%H Paolo Xausa, <a href="/A220001/b220001.txt">Table of n, a(n) for n = 1..10000</a>
%H Chihming Chang and Rami Melhem, <a href="http://citeseerx.ist.psu.edu/pdf/5183c0b2ba11fa5a3ca23e20e040ceb18e60a2fb">Arbitrary Size Benes Networks</a>
%H Hsien-Kuei Hwang, S Janson, TH Tsai, <a href="http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>, Preprint, 2016; Also <a href="https://dx.doi.org/10.1145/3127585">Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications</a>, ACM Transactions on Algorithms, 13:4 (2017), #47
%F 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.
%e 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).
%t 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 *)
%K nonn
%O 1,3
%A _Leonid Broukhis_, Dec 03 2012
|
