This site is supported by donations to The OEIS Foundation. Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing. Other ways to donate

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A061168 Partial sums of floor(log_2(k)) (= A000523(k)). 14
 0, 1, 2, 4, 6, 8, 10, 13, 16, 19, 22, 25, 28, 31, 34, 38, 42, 46, 50, 54, 58, 62, 66, 70, 74, 78, 82, 86, 90, 94, 98, 103, 108, 113, 118, 123, 128, 133, 138, 143, 148, 153, 158, 163, 168, 173, 178, 183, 188, 193, 198, 203, 208, 213, 218, 223, 228, 233, 238, 243, 248 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,3 COMMENTS Given a term b>0 of the sequence and its left hand neighbor c, the corresponding unique sequence index n with property a(n)=b can be determined by n(b)=e+(b-d*(e+1)+2*(e-1))/d, where d=b-c and e=2^d. - Hieronymus Fischer, Dec 05 2006 a(n) gives index of start of binary expansion of n in the binary Champernowne sequence A076478. - N. J. A. Sloane, Dec 14 2017 a(n) is the number of pairs in ancestor relationship (= transitive closure of the parent relationship) in all (binary) heaps on n elements. - Alois P. Heinz, Feb 13 2019 REFERENCES D. E. Knuth, Fundamental Algorithms, Addison-Wesley, 1973, Section 1.2.4, ex. 42(b). LINKS Alois P. Heinz, Table of n, a(n) for n = 1..10000 (first 1000 terms from Harry J. Smith) J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197, ex. 27. Sung-Hyuk Cha, On Integer Sequences Derived from Balanced k-ary Trees, Applied Mathematics in Electrical and Computer Engineering, 2012. Sung-Hyuk Cha, On Complete and Size Balanced k-ary Tree Integer Sequences, International Journal of Applied Mathematics and Informatics, Issue 2, Volume 6, 2012, pp. 67-75. M. Griffiths, More sums involving the floor function, Math. Gaz., 86 (2002), 285-287. Hsien-Kuei Hwang, S. Janson, 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, 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. Eric Weisstein's World of Mathematics, Heap Wikipedia, Binary heap FORMULA a(n) = A001855(n+1) - n. a(n) = Sum_{k=1..n} floor(log_2(k)) = (n+1)*floor(log_2(n)) - 2*(2^floor(log_2(n)) - 1). - Diego Torres (torresvillarroel(AT)hotmail.com), Oct 29 2002 G.f.: 1/(1-x)^2 * Sum(k>=1, x^2^k). - Ralf Stephan, Apr 13 2002 a(n) = A123753(n) - 2*n - 1. - Peter Luschny, Nov 30 2017 MAPLE seq(add(floor(log(k)), k=1..j), j=1..100); # second Maple program: a:= proc(n) option remember; `if`(n<1, 0, ilog2(n)+a(n-1)) end: seq(a(n), n=1..80);   # Alois P. Heinz, Feb 12 2019 MATHEMATICA Accumulate[Floor[Log[2, Range]]] (* Harvey P. Dale, Jul 16 2012 *) a[n_] := (n+1) IntegerLength[n+1, 2] - 2^IntegerLength[n+1, 2] - n + 1; Table[a[n], {n, 1, 61}] (* Peter Luschny, Dec 02 2017 *) PROG (PARI) a(n)=if(n<1, 0, if(n%2==0, a(n/2)+a(n/2-1)+n-1, 2*a((n-1)/2)+n-1)) /* _Ralf Stephan */ (PARI) a(n)=local(k); if(n<1, 0, k=length(binary(n))-1; (n+1)*k-2*(2^k-1)) (PARI) { for (n=1, 1000, k=length(binary(n))-1; write("b061168.txt", n, " ", (n + 1)*k - 2*(2^k - 1)) ) } \\ Harry J. Smith, Jul 18 2009 (Haskell) import Data.List (transpose) a061168 n = a061168_list !! n a061168_list = zipWith (+) [0..] (zipWith (+) hs \$ tail hs) where    hs = concat \$ transpose [a001855_list, a001855_list] -- Reinhard Zumkeller, Jun 03 2013 (Python) def A061168(n):     s, i, z = -n , n, 1     while 0 <= i: s += i; i -= z; z += z     return s print([A061168(n) for n in range(1, 62)]) # Peter Luschny, Nov 30 2017 CROSSREFS Cf. A000523, A001855, A123753, A076478. Sequence in context: A053044 A129011 A130174 * A130798 A165453 A282168 Adjacent sequences:  A061165 A061166 A061167 * A061169 A061170 A061171 KEYWORD nonn,easy AUTHOR Antti Karttunen, Apr 19 2001 STATUS approved

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

Last modified December 6 16:24 EST 2019. Contains 329808 sequences. (Running on oeis4.)