login
A126237
Length of row n in table A126014.
3
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.
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
KEYWORD
nonn
AUTHOR
Dean Hickerson, Dec 21 2006
STATUS
approved