Chapter 2: The Crucial Experiment

Section 1: How Do Simple Programs Behave?

Pascal's triangle and rule 90

As shown on page 611 the pattern produced by rule 90 is exactly Pascal's triangle of binomial coefficients reduced modulo 2: black cells correspond to odd binomial coefficients.

The number of black cells on row t is given by 2^DigitCount[t, 2, 1], where DigitCount[t, 2, 1] is plotted on page 902. The positions of the black cells are given by (and this establishes the connection with the picture on page 117)

Fold[Flatten[{#1 - #2, #1 + #2}]&, {0}, 2^DigitPositions[t]] DigitPositions[n_] := Flatten[Position[Reverse[IntegerDigits[n, 2]], 1]] - 1

The actual pattern generated by rule 90 corresponds to the coefficients in PolynomialMod[Expand[(1/x + x)^t], 2] (see page 1091); the color of a particular cell is thus given by Mod[Binomial[t, (n+t)/2], 2] /; EvenQ[n+t].

Mod[Binomial[t, n], 2] yields a distorted pattern that is the one produced by rule 60 (see page 58). In this pattern, the color of a particular cell can be obtained directly from the digit sequences for t and n by 1-Sign[BitAnd[-t, n]] or (see page 583)

With[{d = Ceiling[Log[2, Max[t, n]+1]]}, If[FreeQ[IntegerDigits[t, 2, d] - IntegerDigits[n, 2, d], -1], 1, 0]]

From Stephen Wolfram: A New Kind of Science [citation]