A126236 Maximum length of a codeword in Huffman encoding of n symbols, where the k-th symbol has frequency k.

1, 2, 3, 3, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11

Offset

2,2

References

M. J. Fisher et al., The birank number of a graph, Congressus Numerant., 204 (2010), 173-180.

Links

Table of n, a(n) for n=2..84.

Wikipedia, Huffman coding

Formula

Conjecture: a(n) = floor(log_2(n)) + floor(log_2(2n/3)). Equivalently, a(n) = a(n-1) + 1 if n has the form 2^k or 3*2^k, a(n) = a(n-1) otherwise. This is true at least for n up to 1000.

Example

A Huffman code for n=8 is (1->00000, 2->00001, 3->0001, 4->001, 5->010, 6->011, 7->10, 8->11). The longest codewords have length a(8)=5.

Crossrefs

Cf. A126014 and A126237. The minimum length of a codeword is in A126235.

Sequence in context: A061716 A362692 A341053 * A198194 A073047 A038567

Adjacent sequences: A126233 A126234 A126235 * A126237 A126238 A126239

Keyword

nonn

Author

Dean Hickerson, Dec 21 2006

Status

approved