cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

A126014 Triangle read by rows, based on Huffman encoding. See comments.

Original entry on oeis.org

2, 3, 2, 2, 3, 2, 5, 2, 6, 3, 2, 8, 3, 2, 9, 5, 2, 5, 2, 6, 3, 2, 8, 3, 2, 9, 5, 2, 11, 5, 2, 12, 6, 3, 2, 14, 6, 3, 2, 15, 8, 3, 2, 17, 8, 3, 2, 18, 9, 5, 2, 20, 9, 5, 2, 21, 11, 5, 2, 11, 5, 2, 12, 6, 3, 2, 14, 6, 3, 2, 15, 8, 3, 2, 17, 8, 3, 2, 18, 9, 5, 2, 20, 9, 5, 2, 21, 11, 5, 2
Offset: 1

Views

Author

Serhat Sevki Dincer (mesti_mudam(AT)yahoo.com), Dec 14 2006

Keywords

Comments

Row #n pertains to Huffman encoding of n symbols, where the k-th symbol has frequency k. Let b(k) be the number of bits used to encode the symbol of frequency k. The row has the values of k such that b(k)>b(k+1).
Each row is ordered descendingly; each ends with '2'. Row #3 is first.

Examples

			In row #8, the frequencies are 1,2,3,4,5,6,7,8 and a Huffman encoding is (1->00000, 2->00001, 3->0001, 4->001, 5->010, 6->011, 7->10, 8->11). The codes shrink after k=6,3,2; so row #8 has 6,3,2.
2; 3,2; 2; 3,2; 5,2; 6,3,2; 8,3,2; 9,5,2; 5,2; 6,3,2; 8,3,2; ...

Links

Crossrefs

The length of the n-th row is in A126237. The minimum and maximum lengths of codewords are in A126235 and A126236.

Extensions

Edited by Don Reble, Dec 17 2006 and Dean Hickerson, Dec 21 2006

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

Original entry on oeis.org

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

Views

Author

Dean Hickerson, Dec 21 2006

Keywords

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

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.

A126237 Length of row n in table A126014.

Original entry on oeis.org

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

Views

Author

Dean Hickerson, Dec 21 2006

Keywords

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

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.
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.