%I A003314 M1345
%S A003314 0,2,5,8,12,16,20,24,29,34,39,44,49,54,59,64,70,76,82,88,94,100,106,112,
%T A003314 118,124,130,136,142,148,154,160,167,174,181,188,195,202,209,216,223,
%U A003314 230,237,244,251,258,265,272,279,286,293,300,307,314,321,328,335
%N A003314 Binary entropy function: for n >= 1, a(n) = n + min { a(k)+a(n-k) : 1 
               <= k <= n-1 }.
%C A003314 Morris gives many other interesting properties of this function.
%D A003314 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A003314 D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, 
               MA, Vol. 3, Sect 5.4.9, Eq. (19). p. 374.
%D A003314 R. Morris, Some theorems on sorting, SIAM J. Appl. Math., 17 (1969), 
               1-6.
%H A003314 T. D. Noe, <a href="b003314.txt">Table of n, a(n) for n=1..1000</a>
%F A003314 a(1) = 0; a(n) = n + a([n/2]) + a(n-[n/2]). [Morris]
%F A003314 a(n) is a convex function of n. [Morris]
%F A003314 a(n)=A001855(n)+n-1. - Michael Somos Feb 07 2004
%F A003314 a(n) = n+a(floor[n/2])+a(ceiling[n/2]) = n*floor[log_2(4n)]-2^floor[log_2(2n)] 
               = A033156(n)-n = n*A070941(n)-A062383(n). - Henry Bottomley (se16(AT)btinternet.com), 
               Jul 03 2002
%F A003314 a(1) = 0 and for n>1: a(n) = a(n-1) + A070941(2*n-1). Also a(n) = A123753(n-1) 
               - 1. - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Oct 
               12 2006
%e A003314 E.g. a(6) = 6 + min {1+12, 2+8, 5+5} = 6 +10 = 16.
%p A003314 A003314 := proc(n) local i,j; option remember; if n<=2 then n elif n=3 
               then 5 else j := 10^10; for i from 1 to n-1 do if A003314(i)+A003314(n-i) 
               < j then j := A003314(i)+A003314(n-i); fi; od; n+j; fi; end;
%o A003314 (PARI) a(n)=if(n<2,0,n+a(n\2)+a((n+1)\2))
%o A003314 (PARI) a(n)=local(m);if(n<2,0,m=length(binary(n-1));n*m-2^m+n)
%Y A003314 Cf. A054248, A097071.
%Y A003314 Sequence in context: A087347 A062468 A061717 this_sequence A070977 A134925 
               A108577
%Y A003314 Adjacent sequences: A003311 A003312 A003313 this_sequence A003315 A003316 
               A003317
%K A003314 nonn,easy,nice
%O A003314 1,2
%A A003314 N. J. A. Sloane (njas(AT)research.att.com).