A126014 -id:A126014 - cp's OEIS frontend

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

Dean Hickerson, Dec 21 2006

nonn

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.

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

Wikipedia, Huffman coding

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

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.

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

Dean Hickerson, Dec 21 2006

nonn

			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.

M. J. Fisher et al., The birank number of a graph, Congressus Numerant., 204 (2010), 173-180.
Wikipedia, Huffman coding

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

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

Dean Hickerson, Dec 21 2006

nonn

			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.

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

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

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.

A126268 Triangle read by rows: row n gives lengths of Huffman codes with n (>= 3) symbols, where symbol[k] has frequency k (k=1,..,n), in increasing k.

Original entry on oeis.org

2, 2, 1, 3, 3, 2, 1, 3, 3, 2, 2, 2, 4, 4, 3, 2, 2, 2, 4, 4, 3, 3, 3, 2, 2, 5, 5, 4, 3, 3, 3, 2, 2

Offset: 3

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

			Possible huffman codes for n = 3,4,5 are:
1 : 00
2 : 01
3 : 1
1 : 100
2 : 101
3 : 11
4 : 0
1 : 000
2 : 001
3 : 01
4 : 10
5 : 11
so the triangle is:
row #3: 2,2,1
row #4: 3,3,2,1
row #5: 3,3,2,2,2
etc.

Wikipedia, Huffman Coding

Cf. A126014.

A126269 Numbers n such that hcl(n,n) < hcl(n,n-1) where hcl(n,i) is the Huffman code length; see comments.

Original entry on oeis.org

3, 4, 9, 10, 21, 22, 45, 46, 93, 94, 189, 190, 381, 382, 765, 766, 1533, 1534, 3069, 3070, 6141, 6142, 12285, 12286, 24573, 24574, 49149, 49150

Offset: 3

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

Consider a string which consists of n distinct symbols such that symbol(i) has frequency i (i=1,2,...,n). Then hcl(n,i) is the Huffman code length of symbol(i).

			Possible Huffman codes for n = 3,4,5 are:
1 : 00
2 : 01
3 : 1
--------
1 : 100
2 : 101
3 : 11
4 : 0
--------
1 : 000
2 : 001
3 : 01
4 : 10
5 : 11
hcl(3,3)=1 < 2=hcl(3,2) and hcl(4,4)=1 < 2=hcl(4,3); so 3,4 are in the sequence.
hcl(5,5)=2=hcl(5,4) so 5 is not in the sequence.

Sean A. Irvine, Java program (github)

Cf. A126268 A126014 A068156 A033484.

Conjecture: a(2k) = A033484(k-1) and a(2k-1) = A068156(k-1), k >= 2.
Conjectures from Colin Barker, Aug 06 2019: (Start)
G.f.: x^3*(3 + 4*x - 2*x^3) / ((1 - x)*(1 + x)*(1 - 2*x^2)).
a(n) = 3*a(n-2) - 2*a(n-4) for n>6.
a(n) = -5/2 + (-1)^n/2 + 3*2^((1/2)*(n-5))*(2-2*(-1)^n + sqrt(2) + (-1)^n*sqrt(2)) for n>2.
(End)

More terms from Sean A. Irvine, Aug 05 2019

A263129 Numbers whose binary representation is the concatenation of all the words in one of its possible Huffman encodings.

Original entry on oeis.org

1024538, 1024675, 1024789, 1024837, 1024936, 1025347, 1025378, 1025384, 1026593, 10234987, 10236597, 10236758, 10258346, 10259347, 10267845, 10278534, 10283546, 10293486, 10293675, 10294837

Offset: 1

Francesco Di Matteo, Oct 10 2015

This sequence is obtained using Huffman coding with decimal numbers as input.
Huffman coding is largely used for lossless data compression and with its algorithm we obtain "Huffman trees" whose branches generate sets of "0-1 words" (codewords), all different, each of them corresponding to a different input symbol.
The Huffman tree is constructed in such a way that the shortest codewords in the output sets match the more frequent symbol in the input (this is the point of Huffman compression).
Moreover, Huffman coding is structured for using codewords that avoid ambiguities (useful for decompression algorithm). E.g., if we have the word "01" in a set, we don't have "010" or "011" (or other longer words that start with "01") in the same set.
In our case, an output codeword set depends especially on the number of different digits and weight of each of them.
So if, for every number n, joining each codeword of one of its output codeword sets in the corresponding decimal digit position, we obtain a "bitstream" that matches to the same n input number binary representation, the number is added to the sequence.
Now, a brief analysis of the first few terms in the sequence.
Huf(Dec[6.0])=16 means "All 6-decimal-digit numbers, 0 repeated, correspond to 16 binary digits of a Huffman coding output". A wordset is, e.g., [00, 01, 100, 101, 110, 111].
But the lowest Dec[6.0] number is 102345, that is, the 17 binary digits 11000111111001001 (i.e., Bin(Dec[6.0])=17).
Also, Huf(Dec[6.(1,2)])=14 (this means "All 6 digits, 1 digit two times") and lowest Bin(Dec[6.(1,2)])=17. The other cases from [6.(2,2)] to [6.(1,6)] are all unbalanced. Thus, the sequence includes no numbers that are 1 to 6 digits in length.
Since with Huf(Dec[7.0])=20, and lowest Bin(Dec[7.0])=20, the first entry of this sequence is 1024538, that is the binary number 11111010001000011010 with the wordset [10, 111, 110, 011, 010, 001, 000].
All the other [7.x] cases are unbalanced, so there are only 9 numbers of 7 decimal digits (different or not) in the sequence.
For Huf(Dec[8.0])=24, we have only the codeword set [111, 110, 101, 011, 001, 010, 100, 000], that generates 297 valid n numbers that are in the sequence (see Program).
E.g., Huf(Dec[9.(1,2)])=27 using a set like [10, 110, 000, 001, 010, 011, 1110, 1111] where the word "10" is used two times in the corresponding decimal digit position, as in 132689520 (see Example).
Is not clear if, with the growth of the length (number of decimal digits) of decimal numbers, and the corresponding growth of the length (number of binary digits) of binary numbers, Huffman coding performs a better compression, and if this sequence is finite or not.

			Decimal   Binary                 Huffman
1024538 = 11111010001000011010 = 111.110.10.001.000.011.010
1024675 = 11111010001010100011 = 111.110.100.010.101.00.011
..
1026593 = 11111010101000100001 = 111.110.101.01.000.100.001
10234987 = 100111000010110001101011 = 100.111.000.010.110.001.101.011
10236597 = 100111000011001010110101 = 100.111.000.011.001.010.110.101
..
132689520 = 111111010001010111001110000 = 1111.110.10.001.010.1110.011.10.000
..
369752480 = 10110000010011111100110100000 = 101.100.0001.001.111.110.011.010.0000
etc.

Francesco Di Matteo, Playful Sequences, Game Edizioni (forthcoming), pages 24-25.

Francesco Di Matteo, Table of n, a(n) for n = 1..306
Slawek Ligus, Huffman tree generator
Rosettacode, Huffman coding, a large collection of Huffman coding programming routines.
Wikipedia, Huffman coding

Cf. A126014.

import itertools
decimal = []
huf = ['000','001','010','011','100','101','110','111']
  # This huf list has been processed by a Huffman coding function.
  # In order to find all the eight n different digits numbers, as I say
  # in Comments, this is the only Huffman encoding valid wordset, so this
  # is the simplest example routine.
ndec = list(map("".join, itertools.permutations('0123456789',len(huf))))
nbin = list(map("".join, itertools.permutations(huf)))
for item in nbin:
  decimal.append(str(int(item, 2)))
n = set(decimal).intersection(set(ndec))
print(sorted(n), len(n))
# Francesco Di Matteo, Oct 18 2015

cp's OEIS Frontend

A126237 Length of row n in table A126014.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A126268 Triangle read by rows: row n gives lengths of Huffman codes with n (>= 3) symbols, where symbol[k] has frequency k (k=1,..,n), in increasing k.

Views

Author

Keywords

Examples

Links

Crossrefs

A126269 Numbers n such that hcl(n,n) < hcl(n,n-1) where hcl(n,i) is the Huffman code length; see comments.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A263129 Numbers whose binary representation is the concatenation of all the words in one of its possible Huffman encodings.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Python