id:A061338 - OEIS Search Results

Search: id:A061338

Displaying 1-1 of 1 results found.

page 1

Increase in maximal number of comparisons for sorting n elements by list merging.

+0
2

0, 1, 2, 2, 4, 2, 3, 3, 8, 2, 3, 3, 5, 3, 4, 4, 16, 2, 3, 3, 5, 3, 4, 4, 9, 3, 4, 4, 6, 4, 5, 5, 32, 2, 3, 3, 5, 3, 4, 4, 9, 3, 4, 4, 6, 4, 5, 5, 17, 3, 4, 4, 6, 4, 5, 5, 10, 4, 5, 5, 7, 5, 6, 6, 64, 2, 3, 3, 5, 3, 4, 4, 9, 3, 4, 4, 6, 4, 5, 5, 17, 3, 4, 4, 6, 4, 5, 5, 10, 4, 5, 5, 7, 5, 6, 6, 33, 3, 4, 4 (list; graph; listen)

	OFFSET	`0,3`
	FORMULA	`a(n) = A003071(n) - A003071(n - 1) = A006519(n) + A000120(n) - 1. If n is a power of 2 then a(n) = n, otherwise a(n) = a(A053645(n)) + 1 where A053645(n) = n - 2^[log2(n)] is the amount by which n exceeds a power of 2.` `G.f.: x/(1-x)^2 + 1/(1-x)Sum(k>=1, (-1+(1-x)2^(k-1))*x^2^k/(1-x^2^k)). - Ralf Stephan (ralf(AT)ark.in-berlin.de), Apr 17 2003`
	CROSSREFS	`Cf. A003071.` `Adjacent sequences: A061335 A061336 A061337 this_sequence A061339 A061340 A061341` `Sequence in context: A123674 A092607 A057939 this_sequence A135714 A103274 A046820`
	KEYWORD	`nonn`
	AUTHOR	`Henry Bottomley (se16(AT)btinternet.com), Apr 27 2001`

page 1

Search completed in 0.002 seconds

Last modified May 16 23:01 EDT 2008. Contains 139884 sequences.

AT&T Labs Research