|
|
A070950
|
|
Triangle read by rows giving successive states of cellular automaton generated by "Rule 30".
|
|
21
|
|
|
1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,1
|
|
COMMENTS
|
If cell and right-hand neighbor are both 0 then new state of cell = state of left-hand neighbor; otherwise new state is complement of that of left-hand neighbor.
A simple rule which produces apparently random behavior. "... probably the single most surprising discovery I have ever made" - Stephen Wolfram.
Row n has length 2n+1.
A110240(n) = A245549(n) = value of row n, seen as binary number. - Reinhard Zumkeller, Jun 08 2013
A070952 gives number of ON cells. - N. J. A. Sloane, Jul 28 2014
|
|
REFERENCES
|
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 27.
|
|
LINKS
|
Reinhard Zumkeller, Rows n = 1..120 of triangle, flattened
N. J. A. Sloane, Illustration of initial terms
Eric Weisstein's World of Mathematics, Rule 30
S. Wolfram, A New Kind of Science
Index to Elementary Cellular Automata
Index entries for sequences related to cellular automata
|
|
FORMULA
|
From Mats Granvik, Dec 06 2019: (Start)
The following recurrence expresses the rules in rule 30, except that instead of If, Or, And, Not, we use addition, subtraction, and multiplication.
T(n, 1) = 0
T(n, 2) = 0
T(1, 3) = 1
T(n, k) = [2*n + 1 >= k] ((1 - (T(n - 1, k - 2)*T(n - 1, k - 1)*T(n - 1, k)))*(1 - T(n - 1, k - 2)*T(n - 1, k - 1)*(1 - T(n - 1, k)))*(1 - (T(n - 1, k - 2)*(1 - T(n - 1, k - 1))*T(n - 1, k)))*(1 - ((1 - T(n - 1, k - 2))*(1 - T(n - 1, k - 1))*(1 - T(n - 1, k))))) + ((T(n - 1, k - 2)*(1 - T(n - 1, k - 1))*(1 - T(n - 1, k)))*((1 - T(n - 1, k - 2))*T(n - 1, k - 1)*T(n - 1, k))*((1 - T(n - 1, k - 2))*T(n - 1, k - 1)*(1 - T(n - 1, k)))*((1 - T(n - 1, k - 2))*(1 - T(n - 1, k - 1))*T(n - 1, k))).
Discarding the term after the plus sign, multiplying/expanding the terms out and replacing all exponents with ones, gives us this simplified recurrence:
T(n, 1) = 0
T(n, 2) = 0
T(1, 3) = 1
T(n, k) = T(-1 + n, -2 + k) + T(-1 + n, -1 + k) - 2 T(-1 + n, -2 + k) T(-1 + n, -1 + k) + (-1 + 2 T(-1 + n, -2 + k)) (-1 + T(-1 + n, -1 + k)) T(-1 + n, k).
That in turn simplifies to:
T(n, 1) = 0
T(n, 2) = 0
T(1, 3) = 1
T(n, k) = Mod(T(-1 + n, -2 + k) + T(-1 + n, -1 + k) + (1 + T(-1 + n, -1 + k)) T(-1 + n, k), 2).
(End)
|
|
EXAMPLE
|
Triangle begins:
1;
1,1,1;
1,1,0,0,1;
1,1,0,1,1,1,1;
...
|
|
MATHEMATICA
|
ArrayPlot[CellularAutomaton[30, {{1}, 0}, 50]] (* N. J. A. Sloane, Aug 11 2009 *)
Clear[t, n, k]; nn = 10; t[1, k_] := t[1, k] = If[k == 3, 1, 0];
t[n_, k_] := t[n, k] = Mod[t[-1 + n, -2 + k] + t[-1 + n, -1 + k] + (1 + t[-1 + n, -1 + k]) t[-1 + n, k], 2]; Flatten[Table[Table[t[n, k], {k, 3, 2*n + 1}], {n, 1, nn}]] (*Mats Granvik, Dec 08 2019*)
|
|
PROG
|
(Haskell)
a070950 n k = a070950_tabf !! n !! k
a070950_row n = a070950_tabf !! n
a070950_tabf = iterate rule30 [1] where
rule30 row = f ([0, 0] ++ row ++ [0, 0]) where
f [_, _] = []
f (u:ws@(0:0:_)) = u : f ws
f (u:ws) = (1 - u) : f ws
-- Reinhard Zumkeller, Feb 01 2013
|
|
CROSSREFS
|
Cf. A070951, A070952 (row sums), A051023 (central terms).
Cf. A071032 (mirror image, rule 86), A226463 (complemented, rule 135), A226464 (mirrored and complemented, rule 149).
Cf. also A245549, A110240.
Sequence in context: A194679 A111940 A129572 * A071031 A187037 A327866
Adjacent sequences: A070947 A070948 A070949 * A070951 A070952 A070953
|
|
KEYWORD
|
nonn,tabf,nice,easy
|
|
AUTHOR
|
N. J. A. Sloane, May 19 2002
|
|
EXTENSIONS
|
More terms from Hans Havermann, May 24 2002
|
|
STATUS
|
approved
|
|
|
|