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

 

Logo

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[2](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[110]]]] (* 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.

License Agreements, Terms of Use, Privacy Policy. .

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