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

Author

Dean Hickerson, Dec 21 2006

Keywords

• nonn

Examples

			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.
		

Links

• Cristina Ballantine, George Beck, Mircea Merca, and Bruce Sagan, Elementary symmetric partitions, arXiv:2409.11268 [math.CO], 2024. See p. 20.
• M. J. Fisher et al., The birank number of a graph, Congressus Numerant., 204 (2010), 173-180.
• Wikipedia, Huffman coding

Crossrefs

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

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.