A070950 Triangle read by rows giving successive states of cellular automaton generated by "Rule 30".

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

Offset: 0

Author

N. J. A. Sloane, May 19 2002

Keywords

• nonn
• tabf
• nice
• easy

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

Examples

			Triangle begins:
        1;
      1,1,1;
    1,1,0,0,1;
  1,1,0,1,1,1,1;
  ...
		

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

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. A363343 (diagonals from the right), A363344 (diagonals from the left).

Cf. A094605 (periods of diagonals from the right), A363345 (eventual periods of diagonals from the left), A363346 (length of initial transients on diagonals from the left).

Cf. also A245549, A110240.

Programs

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

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*)

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)

Extensions

More terms from Hans Havermann, May 24 2002