id:A049802 - OEIS Search Results

Search: id:A049802

Displaying 1-1 of 1 results found.

page 1

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

+0
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; listen)

	OFFSET	`1,5`
	COMMENT	`There is the following connection between this sequence and A080277 : A080277(n) = n + nfloor(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, i.e. T(0):=0, T(n):=2T(floor(n/2))+n, the sequence a(n) seems to be the major obstacle when trying to find a simple, sum-free solution to this recurrence. It seems hard to get rid of the sum. - Peter C. Heinig (algorithms(AT)gmx.de), Oct 21 2006`
	CROSSREFS	`Adjacent sequences: A049799 A049800 A049801 this_sequence A049803 A049804 A049805` `Sequence in context: A140839 A127528 A063070 this_sequence A129240 A127786 A030207`
	KEYWORD	`nonn`
	AUTHOR	`Clark Kimberling (ck6(AT)evansville.edu)`

page 1

Search completed in 0.002 seconds

Last modified October 11 09:12 EDT 2008. Contains 144832 sequences.

AT&T Labs Research