login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003314 Binary entropy function: for n >= 1, a(n) = n + min { a(k)+a(n-k) : 1 <= k <= n-1 }.
(Formerly M1345)
12

%I M1345

%S 0,2,5,8,12,16,20,24,29,34,39,44,49,54,59,64,70,76,82,88,94,100,106,

%T 112,118,124,130,136,142,148,154,160,167,174,181,188,195,202,209,216,

%U 223,230,237,244,251,258,265,272,279,286,293,300,307,314,321,328,335

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

%C Morris gives many other interesting properties of this function.

%D D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, Sect 5.4.9, Eq. (19). p. 374.

%D R. Morris, Some theorems on sorting, SIAM J. Appl. Math., 17 (1969), 1-6.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A003314/b003314.txt">Table of n, a(n) for n=1..1000</a>

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

%F a(n) is a convex function of n. (see the Morris reference)

%F a(n)=A001855(n)+n-1. - _Michael Somos_ Feb 07 2004

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

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

%p 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 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 Table[a[n], {n, 1, 57}] (* _Jean-Fran├žois Alcover_, Oct 15 2012 *)

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

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

%o (Haskell)

%o a003314 n = a003314_list !! (n-1)

%o a003314_list = 0 : f [0] [2..] where

%o f vs (w:ws) = y : f (y:vs) ws where

%o y = w + minimum (zipWith (+) vs $ reverse vs)

%o -- _Reinhard Zumkeller_, Aug 13 2013

%Y Cf. A054248, A097071.

%K nonn,easy,nice

%O 1,2

%A _N. J. A. Sloane_.

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified October 21 19:01 EDT 2014. Contains 248377 sequences.