login
a(1) = 0, a(n) = a(floor(n/2)) + 2*a(ceiling(n/2)) + floor(n/2).
0

%I #16 Sep 08 2022 08:45:11

%S 0,1,3,5,9,12,16,19,27,32,38,42,50,55,61,65,81,90,100,106,118,125,133,

%T 138,154,163,173,179,191,198,206,211,243,260,278,288,308,319,331,338,

%U 362,375,389,397,413,422,432,438,470,487,505,515,535

%N a(1) = 0, a(n) = a(floor(n/2)) + 2*a(ceiling(n/2)) + floor(n/2).

%C Number of comparators used in Bose-Nelson networks.

%C Conjecture: partial sums of A087808. - _Sean A. Irvine_, Jul 14 2022

%H R. C. Bose and R. J. Nelson, <a href="http://dx.doi.org/10.1145/321119.321126">A sorting problem</a>, J. Assoc. Comput. Mach. 9 (1962), 282-296.

%H P. J. Grabner and H.-K. Hwang, <a href="http://algo.stat.sinica.edu.tw/hk/files/2005_07/pdf/Digital_sums_and_divide-and-conquer_recurrences.pdf">Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence</a>, Constructive Approximation, Jan. 2005, Volume 21, Issue 2, pp 149-179.

%o (PARI) a(n)=if(n<2,0,a(floor(n/2))+2*a(ceil(n/2))+floor(n/2))

%o (Magma) [n le 1 select 0 else Self(Floor(n/2)) + 2*Self(Ceiling(n/2)) + Floor(n/2): n in [1..60]]; // _Vincenzo Librandi_, Aug 30 2016

%Y Cf. A064194.

%K nonn,easy

%O 1,3

%A _Ralf Stephan_, Aug 09 2003