cp's OEIS Frontend

A003314 Binary entropy function: a(1)=0; for n > 1, a(n) = n + min { a(k)+a(n-k) : 1 <= k <= n-1 }.

%I A003314 M1345 #84 Mar 30 2023 01:49:24
%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,
%T A003314 112,118,124,130,136,142,148,154,160,167,174,181,188,195,202,209,216,
%U A003314 223,230,237,244,251,258,265,272,279,286,293,300,307,314,321,328,335
%N A003314 Binary entropy function: a(1)=0; 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.
%C A003314 a(n) is a convex function of n. (See the Morris reference.)
%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 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003314 Indranil Ghosh, <a href="/A003314/b003314.txt">Table of n, a(n) for n = 1..32768</a> (terms 1..1000 from T. D. Noe)
%H A003314 Mareike Fischer, <a href="https://arxiv.org/abs/1801.10418">Extremal values of the Sackin balance index for rooted binary trees</a>, arXiv:1801.10418 [q-bio.PE], 2018.
%H A003314 Mareike Fischer, <a href="https://doi.org/10.1007/s00026-021-00539-2">Extremal Values of the Sackin Tree Balance Index</a>, Ann. Comb. (2021) Vol. 25, 515-541, Remark 4.
%H A003314 D. Chistikov, S. Iván, A. Lubiw, and J. Shallit, <a href="https://arxiv.org/abs/1509.07588">Fractional coverings, greedy coverings, and rectifier networks</a>, arXiv preprint arXiv:1509.07588 [cs.CC], 2015-2016.
%H A003314 Hsien-Kuei Hwang, S. Janson, and T.-H. 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.
%H A003314 Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="https://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; DOI: 10.1145/3127585.
%H A003314 D. Knuth, <a href="/A003063/a003063.pdf">Letter to N. J. A. Sloane, date unknown</a>
%H A003314 R. Morris, <a href="http://dx.doi.org/10.1137/0117001">Some theorems on sorting</a>, SIAM J. Appl. Math., 17 (1969), 1-6.
%F A003314 a(1) = 0; a(n) = n + a([n/2]) + a(n-[n/2]). (See the Morris reference.)
%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_, 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_, Oct 12 2006
%F A003314 a(n) = A123753(n-1) - 1. - _Peter Luschny_, Nov 30 2017
%e A003314 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;
%t A003314 a[1] = 0; a[n_] := If[OddQ[n], n + a[(n-1)/2 + 1] + a[(n-1)/2], 2*(n/2 + a[n/2])];
%t A003314 Table[a[n], {n, 1, 57}] (* _Jean-François Alcover_, Oct 15 2012 *)
%t A003314 a[n_] := n + n IntegerLength[n, 2] - 2^IntegerLength[n, 2];
%t A003314 Table[a[n], {n, 1, 57}] (* _Peter Luschny_, Dec 02 2017 *)
%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)
%o A003314 (Haskell)
%o A003314 a003314 n = a003314_list !! (n-1)
%o A003314 a003314_list = 0 : f [0] [2..] where
%o A003314    f vs (w:ws) = y : f (y:vs) ws where
%o A003314      y = w + minimum (zipWith (+) vs $ reverse vs)
%o A003314 -- _Reinhard Zumkeller_, Aug 13 2013
%o A003314 (Python)
%o A003314 def A003314(n):
%o A003314     return n*int(math.log(4*n,2))-2**int(math.log(2*n,2)) # _Indranil Ghosh_, Feb 03 2017
%o A003314 (Python)
%o A003314 def A003314(n):
%o A003314     s, i, z = n-1, n-1, 1
%o A003314     while 0 <= i: s += i; i -= z; z += z
%o A003314     return s
%o A003314 print([A003314(n) for n in range(1, 58)]) # _Peter Luschny_, Nov 30 2017
%o A003314 (Python)
%o A003314 def A003314(n): return n*(1+(m:=(n-1).bit_length()))-(1<<m) # _Chai Wah Wu_, Mar 29 2023
%Y A003314 Cf. A054248, A070941, A123753.
%K A003314 nonn,easy,nice
%O A003314 1,2
%A A003314 _N. J. A. Sloane_