A187200 -id:A187200 - cp's OEIS frontend

A169707 Total number of ON cells at stage n of two-dimensional cellular automaton defined by "Rule 750" using the von Neumann neighborhood.

1, 5, 9, 21, 25, 37, 57, 85, 89, 101, 121, 149, 169, 213, 281, 341, 345, 357, 377, 405, 425, 469, 537, 597, 617, 661, 729, 805, 889, 1045, 1241, 1365, 1369, 1381, 1401, 1429, 1449, 1493, 1561, 1621, 1641, 1685, 1753, 1829, 1913, 2069, 2265, 2389, 2409, 2453, 2521

Offset: 1

N. J. A. Sloane, Apr 17 2010

Square grid, 4 neighbors per cell (N, E, S, W cells), turn ON iff exactly 1 or 3 neighbors are ON; once ON, cells stay ON.
The terms agree with those of A246335 for n <= 11, although the configurations are different starting at n = 7. - N. J. A. Sloane, Sep 21 2014
Offset 1 is best for giving a formula for a(n), although the Maple and Mathematica programs index the states starting at state 0.
It appears that this shares infinitely many terms with both A162795 and A147562, see Formula section and Example section. - Omar E. Pol, Feb 19 2015

			Divides naturally into blocks of sizes 1,2,4,8,16,...:
1,
5, 9,
21, 25, 37, 57,
85, 89, 101, 121, 149, 169, 213, 281, <- terms 8 through 15
341, 345, 357, 377, 405, 425, 469, 537, 597, 617, 661, 729, 805, 889, 1045, 1241,
1365, 1369, 1381, 1401, 1429, 1449, 1493, 1561, 1621, 1641, 1685, 1753, 1829, 1913, 2069, 2265, 2389, 2409, 2453, 2521, ...
From _Omar E. Pol_, Feb 18 2015: (Start)
Also, written as an irregular triangle T(j,k), k>=1, in which the row lengths are the terms of A011782:
1;
5;
9,   21;
25,  37,   57,  85;
89,  101, 121, 149, 169, 213, 281, 341;
345, 357, 377, 405, 425, 469, 537, 597, 617, 661, 729, 805, 889, 1045, 1241, 1365;
The right border gives the positive terms of A002450.
It appears that T(j,k) = A162795(j,k) = A147562(j,k), if k is a power of 2, for example: it appears that the three mentioned triangles only share the elements from the columns 1, 2, 4, 8, 16, ...
(End)

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 928.

N. J. A. Sloane and Vincenzo Librandi, Table of n, a(n) for n = 1..513, computed from the definition, not using the conjectured formula. [The first 200 terms were found by _Vincenzo Librandi_]
David Applegate, The movie version
David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.], arXiv:1004.3036 [math.CO].
N. J. A. Sloane, Table of n, a(n) for n=1..8192 assuming the recurrence is correct. Note that these terms are merely conjectures.
N. J. A. Sloane, Illustration of first 24 generations
N. J. A. Sloane, Illustration of first 24 generations of the NW-NE-SE-SW version of this CA
N. J. A. Sloane, Illustration of generation 7 of the NW-NE-SE-SW version of this CA (containing a(7) = 57 ON cells)
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Index entries for sequences related to cellular automata

Cf. A169708 (first differences), A147562, A147582, A169648, A169649, A169709, A169710, A246333, A246334, A246335, A246336, A253098 (partial sums).
Cf. also A162795, A150552, A160104, A170903, A048645, A187200.
See A253088 for the analogous CA using Rule 750 and a 9-celled neighborhood.

(Maple program that uses the actual definition of the automaton, rather than the (conjectured) formula, from N. J. A. Sloane, Feb 15 2015):
# Count terms in a polynomial:
C := f->`if`(type(f, `+`), nops(f), 1);
# Replace all nonzero coeffts by 1:
bool := proc(f) local ix, iy, f2, i, t1, t2, A;
f2:=expand(f);
if whattype(f) = `+` then
t1:=nops(f2); A:=0;
for i from 1 to t1 do t2:=op(i, f2); ix:=degree(t2, x); iy:=degree(t2, y);
A:=A+x^ix*y^iy; od: A;
else ix:=degree(f2, x); iy:=degree(f2, y); x^ix*y^iy;
fi;
end;
# a loop that produces M steps of A169707 and A169708:
M:=20;
F:=x*y+x/y+1/x*y+1/x/y mod 2;
GG[0]:=1;
for n from 1 to M do dd[n]:=expand(F*GG[n-1]) mod 2;
GG[n]:=bool(GG[n-1]+dd[n]);
lprint(n,C(GG[n]), C(GG[n]-GG[n-1])); od:

Map[Function[Apply[Plus,Flatten[ #1]]], CellularAutomaton[{ 750, {2,{{0,2,0},{2,1,2},{0,2,0}}},{1,1}},{{{1}},0},100]]
ArrayPlot /@ CellularAutomaton[{750, {2, {{0, 2, 0}, {2, 1, 2}, {0, 2, 0}}}, {1, 1}}, {{{1}}, 0}, 23]
(* The next two lines deal with the equivalent CA based on neighbors NW, NE, SE, SW. This is to facilitate the comparison with A246333 and A246335 *)
Map[Function[Apply[Plus, Flatten[ #1]]], CellularAutomaton[{ 750, {2, {{2, 0, 2}, {0, 1, 0}, {2, 0, 2}}}, {1, 1}}, {{{1}}, 0}, 100]]
ArrayPlot /@ CellularAutomaton[{750, {2, {{2, 0, 2}, {0, 1, 0}, {2, 0, 2}}}, {1, 1}}, {{{1}}, 0}, 23]

a(2^k + i) = (4^(k+1)-1)/3 + 4*A246336(i), for k >= 0, 0 <= i < 2^k. For example, if n = 15 = 2^3 + 7, so k=3, i=7, we have a(15) = (4^4-1)/3 + 4*A246336(7) = 85 + 4*49 = 281.
a(n) = 1 + 2*(A139250(n) - A160552(n)) = A160164(n) - A170903(n) = A187220(n) + 2*(A160552(n-1)). - Omar E. Pol, Feb 18 2015
It appears that a(n) = A162795(n) = A147562(n), if n is a member of A048645, otherwise a(n) > A162795(n) > A147562(n). - Omar E. Pol, Feb 19 2015
It appears that a(n) = 1 + 4*A255747(n-1). - Omar E. Pol, Mar 05 2015
It appears that a(n) = 1 + 4*(A139250(n-1) - (a(n-1) - 1)/4), n > 1. - Omar E. Pol, Jul 24 2015
It appears that a(2n) = 1 + 4*A162795(n). - Omar E. Pol, Jul 04 2017

Edited (added formula, illustration, etc.) by N. J. A. Sloane, Aug 30 2014

Offset changed to 1 by N. J. A. Sloane, Feb 09 2015

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

Original entry on oeis.org

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.

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

Original entry on oeis.org

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

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

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

cp's OEIS Frontend

A169707 Total number of ON cells at stage n of two-dimensional cellular automaton defined by "Rule 750" using the von Neumann neighborhood.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

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

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

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