A106182 -id:A106182 - cp's OEIS frontend

A109337 Parse the Thue-Morse sequence (A010060) using the Ziv-Lempel encoding as described in A106182; sequence gives lengths of successive phrases.

1, 1, 2, 3, 2, 2, 3, 4, 2, 3, 3, 5, 3, 3, 4, 4, 4, 5, 4, 4, 6, 5, 6, 4, 4, 5, 6, 7, 5, 7, 6, 5, 4, 7, 6, 7, 5, 7, 5, 6, 7, 6, 6, 8, 5, 8, 4, 6, 7, 5, 8, 5, 6, 7, 6, 9, 7, 8, 6, 5, 8, 6, 7, 7, 7, 6, 8, 8, 8, 9, 7, 10, 6, 9, 9, 7, 8, 10, 8, 8, 9, 8, 9, 8, 9, 7, 9, 8, 7, 10, 9, 10, 8, 9, 7, 8, 9, 8, 9, 11, 9, 11

Offset: 1

N. J. A. Sloane, Aug 24 2005

			The parsing into phrases gives 0, 1, 10, 100, 11, 00, 101, 1010, 01, 011, 001, 10100, ... with lengths 1,1,2,3,2,2,3,4,2,3,3,5,...

Cf. A010060, A106182, A187180-A187188, A187199, A187200.

Terms a(13)-a(102) from John W. Layman, Sep 16 2010

A175844 Parse the base-2 expansion of 1/n using the Ziv-Lempel encoding as described in A106182; sequence gives the eventual period of the differences of the sequence of lengths of the successive phrases.

Original entry on oeis.org

1, 1, 4, 1, 16, 4, 9, 1, 36, 16, 100, 4, 144, 9, 16, 1, 64, 36, 324, 16, 36, 100, 121, 4, 400, 144, 324, 9

Offset: 1

John W. Layman, Sep 24 2010

nonn

The Ziv-Lempel encoding scans the sequence from left to right and inserts a comma when the current phrase (since the last comma) is distinct from all previous phrases (between commas).

It appears that a(n) is just the square of the period of the base 2 expansion of 1/n. For example, if n=3 the sequence of terms in the base-2 expansion of 1/3 is {0,1,0,1,0,1,0,1,...}, of period 2, whereas a(3)=4=2^2.

			For n=3, the sequence of base-2 digits of 1/3 is {0,1,0,1,0,1,0,1,0,1,0,1,...}. The Ziv-Lempel encoding parses this into "phrases": {0}, {1}, {0,1}, {0,1,0}, {1,0}, {1,0,1}, {0,1,0,1}, {0,1,0,1,0}, {1,0,1,0}, {1,0,1,0,1}, {0,1,0,1,0,1}, ..., with lengths {1,1,2,3,2,3,4,5,4,5,6,7,6,7,8,9,8,9,10,11,...}. The differences are {0,1,1,-1,1,1,1,-1,1,1,1,-1,1,...} which quickly becomes periodic with period 4. Thus a(3)=4.

Cf. A106182, A109337.

A095830 Number of binary trees of path length n.

Original entry on oeis.org

1, 2, 1, 4, 4, 2, 14, 8, 12, 28, 21, 52, 52, 72, 92, 160, 212, 178, 446, 360, 628, 920, 918, 1568, 1784, 2676, 2960, 4724, 5360, 7280, 10876, 10936, 17484, 21732, 28469, 34224, 48648, 61232, 78196, 105680, 120904, 178848, 217404, 279312

Offset: 0

Gadiel Seroussi (seroussi(AT)hpl.hp.com), Jul 10 2004

nonn

The cited preprint gives an asymptotic estimate for the number of trees as the path length goes to infinity, for t-ary trees, t >= 2. This sequence corresponds to t=2.

			a(1) = 2 because there are two binary trees of path length 1: a root with a left child and a root with a right child.
a(2) = 1 because there is just one binary tree of path length 2: a root with its two children.

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (terms n = 0..200 from Vincenzo Librandi)
G. Seroussi, On the number of t-ary trees with a given path length, arXiv:cs/0509046 [cs.DM], 2005-2007; Algorithmica 46(3), 557-565, 2006.

Cf. A106182.

terms = 44; B[, ] = 0;
Do[B[w_, z_] = Series[z B[w, w z]^2 + 1, {w, 0, terms-1}, {z, 0, terms-1}] // Normal, {terms-1}];
CoefficientList[B[w, 1] - 1, w] (* Jean-François Alcover, Dec 03 2018 *)

G.f.: B(w, 1) - 1, where B(w, z) satisfies the functional equation B(w, z) = z B(w, wz)^2 + 1. B(w, z) is the g.f. for the number of binary trees of given path length and number of nodes (see Knuth Vol. 1 Sec. 2.3.4.5); B(1, z) is the g.f. for the Catalan numbers; for B(w, w) see A108643.

A109338 Triangle read by rows: T(n,k) = number of inequivalent binary sequences of length n and weight k, where two sequences are said to be equivalent if they have the same set of phrases in their Ziv-Lempel encodings (the phrases can appear in a different order in the two sequences).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 2, 1, 1, 2, 4, 4, 2, 1

Offset: 1

N. J. A. Sloane, Aug 24 2005

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.
See A106182 for further references and links.

			1; 1,1; 1,1,1; 1,2,2,1; 1,2,2,2,1; 1,2,4,4,2,1; ... See A106182 for detailed examples.

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

Row sums give A106182.

A288533 Parse A004736 into distinct phrases [1], [2], [1,3], [2,1], [4], [3], [2,1,5], [4,3], [2,1,6], ...; a(n) is the length of the n-th phrase.

Original entry on oeis.org

1, 1, 2, 2, 1, 1, 3, 2, 3, 1, 3, 2, 1, 2, 2, 2, 1, 2, 4, 1, 1, 2, 3, 3, 2, 3, 5, 1, 3, 3, 3, 1, 1, 2, 2, 4, 3, 2, 3, 4, 4, 1, 3, 4, 4, 2, 1, 2, 2, 5, 5, 1, 2, 4, 3, 5, 1, 1, 2, 3, 4, 5, 2, 2, 3, 5, 5, 3, 1, 3, 3, 3, 4, 5, 1, 2, 2, 4, 5, 6, 1, 2, 4, 4, 6, 4, 1, 2, 3, 4, 4, 6, 2, 1, 2, 3, 3, 5, 5, 4, 1, 2, 3, 5, 6, 6, 1, 1, 2, 3, 4, 5, 7, 3, 2, 3, 4, 4, 7, 6, 1, 3, 3, 4, 5, 6, 5, 1, 2, 2

Offset: 1

Lewis Chen, Jun 11 2017

nonn

The phrases are formed by the Ziv-Lempel encoding described in A106182. - Neal Gersh Tolunsky, Nov 30 2023

			Consider the infinite sequence [1,2,1,3,2,1,4,3,2,1,5,4,3,2,1,...], i.e., A004736. We can first take [1] since we've never used it before. Then [2]. For the third term, we've already used [1], so we must instead take [1,3].

Neal Gersh Tolunsky, Table of n, a(n) for n = 1..10000

Cf. A109337, A106182, A187180, A187181, A187182, A187183, A187184, A187185, A187186, A187187, A187188, A187199, A187200.

# you should use program from internal format
a = set()
i = 2
s = "1"
seq = ""
while i < 100:
    j = i
    while j > 0:
        if s not in a:
            seq = seq + "," + str(len(s)-len(s.replace(",",""))+1)
            a.add(s)
            s = str(j)
        else:
            s = s + "," + str(j)
        j -= 1
    i += 1
print(seq[1:])

cp's OEIS Frontend

A109337 Parse the Thue-Morse sequence (A010060) using the Ziv-Lempel encoding as described in A106182; sequence gives lengths of successive phrases.

Views

Author

Keywords

Examples

Crossrefs

Extensions

A175844 Parse the base-2 expansion of 1/n using the Ziv-Lempel encoding as described in A106182; sequence gives the eventual period of the differences of the sequence of lengths of the successive phrases.

Views

Author

Keywords

Comments

Examples

Crossrefs

A095830 Number of binary trees of path length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A109338 Triangle read by rows: T(n,k) = number of inequivalent binary sequences of length n and weight k, where two sequences are said to be equivalent if they have the same set of phrases in their Ziv-Lempel encodings (the phrases can appear in a different order in the two sequences).

Views

Author

Keywords

Comments

Examples

References

Crossrefs

A288533 Parse A004736 into distinct phrases [1], [2], [1,3], [2,1], [4], [3], [2,1,5], [4,3], [2,1,6], ...; a(n) is the length of the n-th phrase.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python