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

1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6

Offset

2,4

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..103.

Wikipedia, Huffman coding

Formula

Conjecture: a(n) = A099396(n+1) = floor(log_2(2(n+1)/3)). Equivalently, a(n) = a(n-1) + 1 if n has the form 3*2^k-1, 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 shortest codewords have length a(8)=2.

Crossrefs

Cf. A099396, A126014 and A126237. The maximum length of a codeword is in A126236.

Sequence in context: A081604 A123119 A099396 * A220104 A191228 A340763

Adjacent sequences: A126232 A126233 A126234 * A126236 A126237 A126238

Keyword

nonn

Author

Dean Hickerson, Dec 21 2006

Status

approved