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

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

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 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
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 shortest codewords have length a(8)=2.

Links

Crossrefs

Cf. A099396, A126014 and A126237. The maximum length of a codeword is in A126236.

Formula

Conjecture: a(n) = A099396(n+1) = floor(log_2(2(n+1)/3)). Equivalently, a(n) = a(n-1) + 1 if n has the form 3*2^k-1, a(n) = a(n-1) otherwise. This is true at least for n up to 1000.

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.
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.