cp's OEIS Frontend

A061168 Partial sums of floor(log_2(k)) (= A000523(k)).

%I A061168 #81 Jul 23 2025 09:20:41
%S A061168 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,
%T A061168 78,82,86,90,94,98,103,108,113,118,123,128,133,138,143,148,153,158,
%U A061168 163,168,173,178,183,188,193,198,203,208,213,218,223,228,233,238,243,248
%N A061168 Partial sums of floor(log_2(k)) (= A000523(k)).
%C A061168 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
%C A061168 a(n) gives index of start of binary expansion of n in the binary Champernowne sequence A076478. - _N. J. A. Sloane_, Dec 14 2017
%C A061168 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
%D A061168 D. E. Knuth, Fundamental Algorithms, Addison-Wesley, 1973, Section 1.2.4, ex. 42(b).
%H A061168 Alois P. Heinz, <a href="/A061168/b061168.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from Harry J. Smith)
%H A061168 Jean-Paul Allouche and Jeffrey Shallit, <a href="https://doi.org/10.1016/0304-3975(92)90001-V">The ring of k-regular sequences</a>, Theoretical Computer Sci., 98 (1992), 163-197, ex. 27.
%H A061168 Sung-Hyuk Cha, <a href="http://www.wseas.us/e-library/conferences/2012/CambridgeUSA/MATHCC/MATHCC-60.pdf">On Integer Sequences Derived from Balanced k-ary Trees</a>, Applied Mathematics in Electrical and Computer Engineering, 2012.
%H A061168 Sung-Hyuk Cha, <a href="http://naun.org/multimedia/UPress/ami/16-125.pdf">On Complete and Size Balanced k-ary Tree Integer Sequences</a>, International Journal of Applied Mathematics and Informatics, Issue 2, Volume 6, 2012, pp. 67-75.
%H A061168 Alan M. Cleary, Joseph Winjum, Jordan Dood, Hiroki Shibata, and Shunsuke Inenaga, <a href="https://doi.org/10.4230/LIPIcs.SEA.2025.12">Bit Packed Encodings for Grammar-Compressed Strings Supporting Fast Random Access</a>, Leibniz Int'l Proc. Informatics (LIPIcs) 23rd Int'l Symp. on Experim. Algor. (SEA 2025) Art. No. 12, 12:1-12:17. See p. 12:8.
%H A061168 Martin Griffiths, <a href="http://www.jstor.org/stable/3621862">More sums involving the floor function</a>, Math. Gaz., 86 (2002), 285-287.
%H A061168 Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>, Preprint 2016.
%H A061168 Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="https://doi.org/10.1145/3127585">Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications</a>, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
%H A061168 Tamás Lengyel, <a href="http://math.colgate.edu/~integers/y27/y27.pdf">On the 2-Adic Valuation of Differences of Harmonic Numbers</a>, Integers (2024) Vol. 24, A27. See p. 8.
%H A061168 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Heap.html">Heap</a>
%H A061168 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%F A061168 a(n) = A001855(n+1) - n.
%F A061168 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
%F A061168 G.f.: 1/(1-x)^2 * Sum(k>=1, x^2^k). - _Ralf Stephan_, Apr 13 2002
%F A061168 a(n) = A123753(n) - 2*n - 1. - _Peter Luschny_, Nov 30 2017
%p A061168 seq(add(floor(log[2](k)),k=1..j),j=1..100);
%p A061168 # second Maple program:
%p A061168 a:= proc(n) option remember; `if`(n<1, 0, ilog2(n)+a(n-1)) end:
%p A061168 seq(a(n), n=1..80);   # _Alois P. Heinz_, Feb 12 2019
%t A061168 Accumulate[Floor[Log[2,Range[110]]]] (* _Harvey P. Dale_, Jul 16 2012 *)
%t A061168 a[n_] := (n+1) IntegerLength[n+1, 2] - 2^IntegerLength[n+1, 2] - n + 1;
%t A061168 Table[a[n], {n, 1, 61}] (* _Peter Luschny_, Dec 02 2017 *)
%o A061168 (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 */
%o A061168 (PARI) a(n)=local(k); if(n<1,0,k=length(binary(n))-1; (n+1)*k-2*(2^k-1))
%o A061168 (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
%o A061168 (Haskell)
%o A061168 import Data.List (transpose)
%o A061168 a061168 n = a061168_list !! n
%o A061168 a061168_list = zipWith (+) [0..] (zipWith (+) hs $ tail hs) where
%o A061168    hs = concat $ transpose [a001855_list, a001855_list]
%o A061168 -- _Reinhard Zumkeller_, Jun 03 2013
%o A061168 (Python)
%o A061168 def A061168(n):
%o A061168     s, i, z = -n , n, 1
%o A061168     while 0 <= i: s += i; i -= z; z += z
%o A061168     return s
%o A061168 print([A061168(n) for n in range(1, 62)]) # _Peter Luschny_, Nov 30 2017
%o A061168 (Python)
%o A061168 def A061168(n): return (n+1)*((m:=n.bit_length())-1)-(1<<m)+2 # _Chai Wah Wu_, Mar 29 2023
%Y A061168 Cf. A000523, A001855, A123753, A076478.
%K A061168 nonn,easy
%O A061168 1,3
%A A061168 _Antti Karttunen_, Apr 19 2001