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

Table of n, a(n) for n=3..30.

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

Cf. A126268 A126014 A068156 A033484.

Sequence in context: A047230 A277138 A327282 * A319618 A172980 A336930

Adjacent sequences: A126266 A126267 A126268 * A126270 A126271 A126272

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