

A049802


a(n)=n mod 2 + n mod 4 + ... + n mod 2^k, where 2^k<=n<2^(k+1).


1



0, 0, 1, 0, 2, 2, 4, 0, 3, 4, 7, 4, 7, 8, 11, 0, 4, 6, 10, 8, 12, 14, 18, 8, 12, 14, 18, 16, 20, 22, 26, 0, 5, 8, 13, 12, 17, 20, 25, 16, 21, 24, 29, 28, 33, 36, 41, 16, 21, 24, 29, 28, 33, 36, 41, 32, 37, 40, 45, 44, 49, 52, 57, 0, 6, 10, 16, 16
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,5


COMMENTS

There is the following connection between this sequence and A080277 : A080277(n) = n + n*floor(lg(n))  a(n), where lg is the logarithm to base 2. Since A080277(n) is the solution to a prototypical recurrence in the analysis of the algorithm Merge Sort, that is, T(0):=0, T(n):=2*T(floor(n/2))+n, the sequence a(n) seems to be the major obstacle when trying to find a simple, sumfree solution to this recurrence. It seems hard to get rid of the sum.  Peter C. Heinig (algorithms(AT)gmx.de), Oct 21 2006


LINKS

Paolo P. Lava, Table of n, a(n) for n = 1..1000


MAPLE

with(numtheory); P:=proc(q) local a, b, c, n; a:=0;
for n from 1 to q do a:=convert(n, binary, decimal); b:=1; c:=0;
while (a mod 10^b)<a do c:=c+convert((a mod 10^b), decimal, binary);
b:=b+1; od; print(c); od; end: P(1000); #Paolo P. Lava, Aug 22 2013


MATHEMATICA

Table[n * Floor@Log[2, n]  Sum[Floor[n*2^k]*2^k, {k, Log[2, n]}], {n, 100}] (* Federico Provvedi, Aug 17 2013 *)


CROSSREFS

Sequence in context: A246846 A127528 A063070 * A129240 A246816 A127786
Adjacent sequences: A049799 A049800 A049801 * A049803 A049804 A049805


KEYWORD

nonn


AUTHOR

Clark Kimberling


STATUS

approved



