|
Search: id:A003314
|
|
|
| A003314 |
|
Binary entropy function: for n >= 1, a(n) = n + min { a(k)+a(n-k) : 1 <= k <= n-1 }.
(Formerly M1345)
|
|
+0
9
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
Morris gives many other interesting properties of this function.
|
|
REFERENCES
|
D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, Sect 5.4.9, Eq. (19). p. 374.
R. Morris, Some theorems on sorting, SIAM J. Appl. Math., 17 (1969), 1-6.
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=1..1000
|
|
FORMULA
|
a(1) = 0; a(n) = n + a([n/2]) + a(n-[n/2]). [Morris]
a(n) is a convex function of n. [Morris]
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 (se16(AT)btinternet.com), 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 (reinhard.zumkeller(AT)lhsystems.com), Oct 12 2006
|
|
EXAMPLE
|
E.g. a(6) = 6 + min {1+12, 2+8, 5+5} = 6 +10 = 16.
|
|
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;
|
|
PROGRAM
|
(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)
|
|
CROSSREFS
|
Cf. A054248, A097071.
Sequence in context: A087347 A062468 A061717 this_sequence A070977 A134925 A108577
Adjacent sequences: A003311 A003312 A003313 this_sequence A003315 A003316 A003317
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
njas
|
|
|
Search completed in 0.002 seconds
|
