login
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
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
Sean A. Irvine, Java program (github)
FORMULA
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)
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
More terms from Sean A. Irvine, Aug 05 2019
STATUS
approved