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