|
%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
|
