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

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

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 December 21 05:45 EST 2014. Contains 252296 sequences.