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

0, 2, 5, 8, 12, 16, 20, 24, 29, 34, 39, 44, 49, 54, 59, 64, 70, 76, 82, 88, 94, 100, 106, 112, 118, 124, 130, 136, 142, 148, 154, 160, 167, 174, 181, 188, 195, 202, 209, 216, 223, 230, 237, 244, 251, 258, 265, 272, 279, 286, 293, 300, 307, 314, 321, 328, 335

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

Morris gives many other interesting properties of this function.

a(n) is a convex function of n. (See the Morris reference.)

Examples

			a(6) = 6 + min {1+12, 2+8, 5+5} = 6 + 10 = 16.
		

References

• D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, Sect 5.4.9, Eq. (19). p. 374.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Indranil Ghosh, Table of n, a(n) for n = 1..32768 (terms 1..1000 from T. D. Noe)
• Mareike Fischer, Extremal values of the Sackin balance index for rooted binary trees, arXiv:1801.10418 [q-bio.PE], 2018.
• Mareike Fischer, Extremal Values of the Sackin Tree Balance Index, Ann. Comb. (2021) Vol. 25, 515-541, Remark 4.
• D. Chistikov, S. Iván, A. Lubiw, and J. Shallit, Fractional coverings, greedy coverings, and rectifier networks, arXiv preprint arXiv:1509.07588 [cs.CC], 2015-2016.
• Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.
• Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
• D. Knuth, Letter to N. J. A. Sloane, date unknown
• R. Morris, Some theorems on sorting, SIAM J. Appl. Math., 17 (1969), 1-6.

Crossrefs

Cf. A054248, A070941, A123753.

Programs

Haskell

a003314 n = a003314_list !! (n-1)
a003314_list = 0 : f [0] [2..] where
   f vs (w:ws) = y : f (y:vs) ws where
     y = w + minimum (zipWith (+) vs $ reverse vs)
-- Reinhard Zumkeller, Aug 13 2013

Maple

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;

Mathematica

a[1] = 0; a[n_] := If[OddQ[n], n + a[(n-1)/2 + 1] + a[(n-1)/2], 2*(n/2 + a[n/2])];
Table[a[n], {n, 1, 57}] (* Jean-François Alcover, Oct 15 2012 *)
a[n_] := n + n IntegerLength[n, 2] - 2^IntegerLength[n, 2];
Table[a[n], {n, 1, 57}] (* Peter Luschny, Dec 02 2017 *)

PARI

a(n)=if(n<2,0,n+a(n\2)+a((n+1)\2))

PARI

a(n)=local(m);if(n<2,0,m=length(binary(n-1));n*m-2^m+n)

Python

def A003314(n):
    return n*int(math.log(4*n,2))-2**int(math.log(2*n,2)) # Indranil Ghosh, Feb 03 2017

Python

def A003314(n):
    s, i, z = n-1, n-1, 1
    while 0 <= i: s += i; i -= z; z += z
    return s
print([A003314(n) for n in range(1, 58)]) # Peter Luschny, Nov 30 2017

Python

def A003314(n): return n*(1+(m:=(n-1).bit_length()))-(1<Chai Wah Wu, Mar 29 2023

Formula

a(1) = 0; a(n) = n + a([n/2]) + a(n-[n/2]). (See the Morris reference.)

a(n) = A001855(n)+n-1. - Michael Somos Feb 07 2004

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

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

a(n) = A123753(n-1) - 1. - Peter Luschny, Nov 30 2017