0,2

The Ziv-Lempel encoding scans the sequence from left to right, and inserts a comma when the current phrase is an extension by one bit of an earlier phrase. In any case the scan ends with a comma. The phrases are the segments between the commas.

Equivalent sequences necessarily have the same Hamming weight.

J. Ziv and A. Lempel, A universal algorithm for sequential data compression. IEEE Trans. Information Theory IT-23 (1977), 337-343.

G. Seroussi, On universal types, Preprint, 2004.

G. Seroussi, On the number of t-ary trees with a given path length, Algorithmica 46(3), 557-565, 2006.

Seroussi shows that a(n) is asymptotically 2^{2cn/log_2(n)(1+o(1))}, where c = 0.11... is the inverse entropy function of 1/2.

The Ziv-Lempel encodings of the strings of lengths 1 through 3 are:

0,

1, so a(1)=2;

0,0,

0,1,

1,0, (same phrases as in previous line)

1,1, so a(2)=3;

0,00,

0,01,

0,1,0,

1,0,0, (same phrases as in previous line)

0,1,1,

1,0,1, (same phrases as in previous line)

1,10,

1,11, so a(3)=6; ...

(TCL program from David Applegate) proc compress_phrases {vec} {set cur []; foreach v $vec {lappend cur $v

if {![info exists phrases($cur)]} {set phrases($cur) 1; set cur []}}

set plist [array names phrases]; if {[llength $cur]} {lappend plist $cur}

return [lsort $plist]}

proc enum {n vec} {if {$n == 0} {global phraselists

set phraselists([compress_phrases $vec]) 1} else {incr n -1

enum $n [concat $vec [list 0]]; enum $n [concat $vec [list 1]]}}

proc doit {} {global phraselists; set n 0; while {1} {array unset phraselists

enum $n []; puts -nonewline "[array size phraselists], "; flush stdout; incr n}}

doit

Row sums of A109338. Cf. A109337.

Cf. A095830.

Adjacent sequences: A106179 A106180 A106181 this_sequence A106183 A106184 A106185

Sequence in context: A089426 A066739 A066815 this_sequence A097097 A095162 A075723

nonn,hard

njas, Aug 23 2005

Terms from a(6) onwards from David Applegate (david(AT)research.att.com), Aug 29 2005