|
|
A126269
|
|
Numbers n such that hcl(n,n) < hcl(n,n-1) where hcl(n,i) is the Huffman code length; see comments.
|
|
1
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
3,1
|
|
COMMENTS
|
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).
|
|
LINKS
|
|
|
FORMULA
|
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)
|
|
EXAMPLE
|
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.
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
Serhat Sevki Dincer (mesti_mudam(AT)yahoo.com), Dec 22 2006
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|