A070950 - OEIS (original) (raw)

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

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.

REFERENCES

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

LINKS

Eric Weisstein's World of Mathematics, Rule 30

FORMULA

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

IntegerDigits[NestList[BitXor[#, BitOr[2*#, 4*#]] &, 1, 10], 2] (* Paolo Xausa, Feb 05 2026 *)

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

CROSSREFS

Cf. [A071032](/A071032 "Triangle read by rows giving successive states of cellular automaton generated by "Rule 86".") (mirror image, rule 86), [A226463](/A226463 "Triangle read by rows giving successive states of cellular automaton generated by "Rule 135" within range n from the origin.") (complemented, rule 135), [A226464](/A226464 "Triangle read by rows giving successive states of cellular automaton generated by "Rule 149" within range n from the origin.") (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).