login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


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 September 20 09:30 EDT 2021. Contains 347579 sequences. (Running on oeis4.)