A109337 -id:A109337 - cp's OEIS frontend

A187180 Parse the infinite string 0101010101... into distinct phrases 0, 1, 01, 010, 10, ...; a(n) = length of n-th phrase.

1, 1, 2, 3, 2, 3, 4, 5, 4, 5, 6, 7, 6, 7, 8, 9, 8, 9, 10, 11, 10, 11, 12, 13, 12, 13, 14, 15, 14, 15, 16, 17, 16, 17, 18, 19, 18, 19, 20, 21, 20, 21, 22, 23, 22, 23, 24, 25, 24, 25, 26, 27, 26, 27, 28, 29, 28, 29, 30, 31, 30, 31, 32, 33, 32, 33, 34, 35, 34, 35, 36, 37, 36, 37, 38, 39, 38, 39, 40, 41, 40, 41, 42, 43, 42, 43, 44, 45, 44, 45, 46, 47, 46, 47, 48, 49, 48, 49, 50, 51, 50, 51, 52, 53, 52, 53, 54, 55, 54, 55, 56, 57, 56, 57, 58, 59, 58, 59, 60, 61

Offset: 1

N. J. A. Sloane, Mar 06 2011

			The sequence begins
   1   1
   2   3   2   3
   4   5   4   5
   6   7   6   7
   8   9   8   9
  10  11  10  11 ...

Ray Chandler, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (1,0,0,1,-1).

See A187180-A187188 for alphabets of size 2 through 10.
See also A109337, A187199, A187200, A106249, A083219, A018837.
Essentially the same as A106249 and A018837.

1,1,seq(op(2*i*[1,1,1,1]+[0,1,0,1]), i=1..100); # Robert Israel, Oct 15 2015

Join[{1},LinearRecurrence[{1, 0, 0, 1, -1},{1, 2, 3, 2, 3},119]] (* Ray Chandler, Aug 26 2015 *)
CoefficientList[Series[(x^5 - 2 x^4 + x^3 + x^2 + 1)/((x - 1)^2 (x + 1) (x^2 + 1)), {x, 0, 150}], x] (* Vincenzo Librandi, Oct 16 2015 *)

a(n) = if(n==1, 1, (1 + (-1)^n + (1-I)*(-I)^n + (1+I)*I^n + 2*n) / 4); \\ Colin Barker, Oct 15 2015

Vec(x*(x^5-2*x^4+x^3+x^2+1) / ((x-1)^2*(x+1)*(x^2+1)) + O(x^100)) \\ Colin Barker, Oct 15 2015

Consider more generally the string 012...k012...k012...k012...k01... with an alphabet of size B, where k = B-1. The sequence begins with B 1's, and thereafter is quasi-periodic with period B^2, and increases by B in each period.
For the present example, where B=2, the sequence begins with two 1's and thereafter increases by 2 in each block of 4: (1,1) (2,3,2,3), (4,5,4,5), (6,7,6,7), ...
From Colin Barker, Oct 15 2015: (Start)
a(n) = (1+(-1)^n+(1-i)*(-i)^n+(1+i)*i^n+2*n)/4 for n>1, where i = sqrt(-1).
G.f.: x*(x^5-2*x^4+x^3+x^2+1) / ((x-1)^2*(x+1)*(x^2+1)). (End)
From Wesley Ivan Hurt, May 03 2021: (Start)
a(n) = a(n-1)+a(n-4)-a(n-5).
a(n) = floor((n+1+(-1)^floor((n+1)/2))/2) for n > 1. (End)

A187188 Parse the infinite string 0123456789012345678901234567890... into distinct phrases 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 01, 23, 45, 67, 89, 012, 34, 56, 78, 90, 12, 345, ...; a(n) = length of n-th phrase.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, Mar 06 2011

nonn

See A187180-A187187 for further details.

Answers a question raised by Sergio Verdu (personal communication, Mar 05 2011).

			The sequence begins
1   1   1   1   1   1   1   1   1   1
2   2   2   2   2   3   2   2   2   2   2   3
3   3   3   3   3   3   3   3
4   4   4   4   4   5   4   4   4   4   4   5
6   5   5   6   5   5   6   5   5   6   5   5
6   7
6   6   6   6   6
7   7   7   7   7   7   7   7   7
8   8   8   8   8   9   8   8   8   8   8   9
9   9   9   9   9   9   9   9
10  11  10  11  10  11  10  11  10  11 10  11  10  11  10  11  10  11  10  11
12  12  12  12  12  13  12  12  12  12  12  13
...

N. J. A. Sloane, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1).

See A187180-A187188 for alphabets of size 2 through 10.

A187199 Parse the Kolakoski sequence A000002 into distinct phrases 1, 2, 21, 12, 122, 1221, 121, 12212, 11, ...; a(n) = length of n-th phrase.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, Mar 06 2011

nonn

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Rémy Sigrist, PARI program

Cf. A000002, A007782, A109337, A187180-A187188, A187200.

PARI
```
\\ See Links section.
```

A187200 Parse the Fibonacci word A003849 into distinct phrases 0, 1, 00, 10, 100, 1001, 01, 001, 010, ...; a(n) = length of n-th phrase.

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 5, 4, 5, 5, 6, 6, 5, 5, 6, 6, 7, 7, 7, 8, 7, 6, 8, 9, 6, 6, 10, 7, 8, 8, 7, 8, 7, 11, 7, 9, 8, 9, 8, 10, 9, 8, 9, 8, 9, 9, 9, 12, 10, 10, 9, 10, 9, 11, 10, 13, 12, 10, 10, 11, 11, 11, 10, 11, 11, 14, 11, 12, 12, 11, 13, 10, 12, 12, 11, 12, 13, 12, 13, 14, 13, 11, 13, 14, 15, 14, 13, 16, 15, 12, 12, 17

Offset: 1

N. J. A. Sloane, Mar 06 2011

nonn

Cf. A003849, A109337, A187180-A187880, A187199, A187201.

A106182 Number of inequivalent binary sequences of length n, 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, 2, 3, 6, 8, 14, 20, 32, 48, 60, 109, 138, 200, 296, 404, 576, 776, 1170, 1480, 2144, 2912, 3888, 5578, 7204, 10032, 13276

Offset: 0

N. J. A. Sloane, Aug 23 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.

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

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; arXiv:cs/0509046 [cs.DM], 2005-2007.

Row sums of A109338. Cf. A109337.

Cf. A095830.

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
# David Applegate

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.

Terms from a(6) onwards from David Applegate, Aug 29 2005

Terms a(0)-a(20) confirmed and a(21)-a(25) added by John W. Layman, Sep 20 2010

A187201 Parse Gijswijt's sequence A090822 into distinct phrases 1, 12, 11, 2, 22, 3, 112, 1122, 23, ...; a(n) = length of n-th phrase.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, Mar 06 2011

nonn

Index entries for sequences related to Gijswijt's sequence

Cf. A090822, A109337, A187180-A187880, A187199, A187200.

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:])

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.

cp's OEIS Frontend

A187180 Parse the infinite string 0101010101... into distinct phrases 0, 1, 01, 010, 10, ...; a(n) = length of n-th phrase.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A187188 Parse the infinite string 0123456789012345678901234567890... into distinct phrases 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 01, 23, 45, 67, 89, 012, 34, 56, 78, 90, 12, 345, ...; a(n) = length of n-th phrase.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A187199 Parse the Kolakoski sequence A000002 into distinct phrases 1, 2, 21, 12, 122, 1221, 121, 12212, 11, ...; a(n) = length of n-th phrase.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A187200 Parse the Fibonacci word A003849 into distinct phrases 0, 1, 00, 10, 100, 1001, 01, 001, 010, ...; a(n) = length of n-th phrase.

Views

Author

Keywords

Crossrefs

A106182 Number of inequivalent binary sequences of length n, 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

Links

Crossrefs

Programs

Tcl

Formula

Extensions

A187201 Parse Gijswijt's sequence A090822 into distinct phrases 1, 12, 11, 2, 22, 3, 112, 1122, 23, ...; a(n) = length of n-th phrase.

Views

Author

Keywords

Links

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

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