A126237 Length of row n in table A126014.

1, 2, 1, 2, 2, 3, 3, 3, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 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, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6

Offset

3,2

Comments

a(n) is 1 less than the number of distinct codeword lengths in Huffman encoding of n symbols, where the k-th symbol has frequency k.

Links

Table of n, a(n) for n=3..104.

Wikipedia, Huffman coding

Formula

I conjecture that there are no gaps in the set of codeword lengths; that is, every integer that's between the minimum and maximum codeword lengths occurs as a codeword length. If so, then a(n) = A126236(n) - A126235(n). If, in addition, the conjectured formulas for the min and max lengths are correct, then a(n) = floor(log_2(n)) unless n has the form 3*2^k-1, in which case a(n) = floor(log_2(n)) - 1. This is true at least for n up to 1000.

Example

Row 8 of A126014 is (6,3,2), so a(8)=3.

Crossrefs

Cf. A126014. The minimum length of a codeword is in A126235. The maximum length is in A126236.

Sequence in context: A050373 A306433 A308174 * A243164 A333708 A132203

Adjacent sequences: A126234 A126235 A126236 * A126238 A126239 A126240

Keyword

nonn

Author

Dean Hickerson, Dec 21 2006

Status

approved