cp's OEIS Frontend

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

%I A070950 #84 Feb 16 2025 08:32:46
%S A070950 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,
%T A070950 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,
%U A070950 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
%N A070950 Triangle read by rows giving successive states of cellular automaton generated by "Rule 30".
%C A070950 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.
%C A070950 A simple rule which produces apparently random behavior. "... probably the single most surprising discovery I have ever made" - Stephen Wolfram.
%C A070950 Row n has length 2n+1.
%C A070950 A110240(n) = A245549(n) = value of row n, seen as binary number. - _Reinhard Zumkeller_, Jun 08 2013
%C A070950 A070952 gives number of ON cells. - _N. J. A. Sloane_, Jul 28 2014
%D A070950 S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 27.
%H A070950 Reinhard Zumkeller, <a href="/A070950/b070950.txt">Rows n = 1..120 of triangle, flattened</a>
%H A070950 N. J. A. Sloane, <a href="/A070950/a070950.gif">Illustration of initial terms</a>
%H A070950 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Rule30.html">Rule 30</a>
%H A070950 S. Wolfram, <a href="http://wolframscience.com/">A New Kind of Science</a>
%H A070950 <a href="https://oeis.org/wiki/Index_to_Elementary_Cellular_Automata">Index to Elementary Cellular Automata</a>
%H A070950 <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>
%F A070950 From _Mats Granvik_, Dec 06 2019: (Start)
%F A070950 The following recurrence expresses the rules in rule 30, except that instead of If, Or, And, Not, we use addition, subtraction, and multiplication.
%F A070950 T(n, 1) = 0
%F A070950 T(n, 2) = 0
%F A070950 T(1, 3) = 1
%F A070950 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))).
%F A070950 Discarding the term after the plus sign, multiplying/expanding the terms out and replacing all exponents with ones, gives us this simplified recurrence:
%F A070950 T(n, 1) = 0
%F A070950 T(n, 2) = 0
%F A070950 T(1, 3) = 1
%F A070950 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).
%F A070950 That in turn simplifies to:
%F A070950 T(n, 1) = 0
%F A070950 T(n, 2) = 0
%F A070950 T(1, 3) = 1
%F A070950 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).
%F A070950 (End)
%e A070950 Triangle begins:
%e A070950         1;
%e A070950       1,1,1;
%e A070950     1,1,0,0,1;
%e A070950   1,1,0,1,1,1,1;
%e A070950   ...
%t A070950 ArrayPlot[CellularAutomaton[30,{{1},0}, 50]] (* _N. J. A. Sloane_, Aug 11 2009 *)
%t A070950 Clear[t, n, k]; nn = 10; t[1, k_] := t[1, k] = If[k == 3, 1, 0];
%t A070950 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*)
%o A070950 (Haskell)
%o A070950 a070950 n k = a070950_tabf !! n !! k
%o A070950 a070950_row n = a070950_tabf !! n
%o A070950 a070950_tabf = iterate rule30 [1] where
%o A070950    rule30 row = f ([0,0] ++ row ++ [0,0]) where
%o A070950        f [_,_]          = []
%o A070950        f (u:ws@(0:0:_)) = u : f ws
%o A070950        f (u:ws)         = (1 - u) : f ws
%o A070950 -- _Reinhard Zumkeller_, Feb 01 2013
%Y A070950 Cf. A070951, A070952 (row sums), A051023 (central terms).
%Y A070950 Cf. A071032 (mirror image, rule 86), A226463 (complemented, rule 135), A226464 (mirrored and complemented, rule 149).
%Y A070950 Cf. A363343 (diagonals from the right), A363344 (diagonals from the left).
%Y A070950 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).
%Y A070950 Cf. also A245549, A110240.
%K A070950 nonn,tabf,nice,easy
%O A070950 0,1
%A A070950 _N. J. A. Sloane_, May 19 2002
%E A070950 More terms from _Hans Havermann_, May 24 2002