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

Author

Dean Hickerson, Dec 21 2006

Keywords

• nonn

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.

Examples

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

Links

• Wikipedia, Huffman coding

Crossrefs

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

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.