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

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

Author

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

Keywords

• easy
• nonn

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

Examples

			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.
		

Links

• Sean A. Irvine, Java program (github)

Crossrefs

Cf. A126268 A126014 A068156 A033484.

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)

Extensions

More terms from Sean A. Irvine, Aug 05 2019