The Perrin sequence f[n_] := f[n - 2] + f[n - 3] ; f[0] = 3; f[1] = 0 ; f[2] = 2 has the peculiar property that Mod[f[n], n]  0 mostly but not always only for n prime.

But it turns out that similar phenomena can also be found in systems that involve only whole numbers. … But if the number is odd, then first add 1—so as to get an even number—and only then multiply by 3/2 . … The digit is 0 when the number is even and 1 when it is odd, and, as shown, the digits alternate in a seemingly random way.

Checking [tilings with] constraints A set of allowed templates can be specified by a Mathematica pattern of the form t 1 | t 2 | t 3 etc. where the t i are for example {{_, 1, _}, {0, 0, 1}, {_, 0, _}} . To check whether an array list contains only arrangements of colors corresponding to allowed templates one can then use SatisfiedQ[list_, allowed_] := Apply[And, Map[MatchQ[#, allowed] &, Partition[list, {3, 3}, {1, 1}], {2}], {0, 1}]

In base 10, there are 10 possible digits: 0 through 9. … In base 2, as used in practical computers, there are just two possible digits: 0 and 1. And in this base, successive digits starting from the right have coefficients 1 , 2 , 4 = 2×2 , 8 = 2×2×2 , etc.

(The lag systems studied in 1963 by Hao Wang allow dependence on more than just the first element, but remove only the first element.) … But then he looked at rules that remove three elements at each step, and he discovered the rule {3, {{0, _, _}  {0, 0}, {1, _, _}  {1, 1, 0, 1}}} . … An example is {2, {{0, _}  {2, 1}, {1, _}  {0}, {2, _}  {0, 2, 1, 2}}} .

Such a limiting pattern exists only within the unit circle Abs[c] < 1 . … The magnitude of this gap turns out to be given by With[{d = Conjugate[c], r = 1 - Abs[c] 2 }, Which[Im[c] < 0, d, Im[c]  0, 0, Re[c] > 0, With[{n = Ceiling[ π /2/Arg[c]]}, Im[c(1 - d n )/(1 - d)] + Im[c d n (1 + d)]/r], Arg[c] > 3 π /4, Im[c + c 2 ]/r, True, Im[c] + Im[c 2 + c 3 ]/r]] The picture below shows the region for which the gap is positive, corresponding to trees which are not connected. … The bottom boundary of the region lies along Re[c] = -1/2 ; the extremal point on the edge of the gap in this case corresponds to {0, 0, 1, 0, 1, 0, 1, …} where the last two elements repeat forever.

Systems of Limited Size and Class 2 Behavior…And in fact in most class 2 cellular automata these patterns are effectively only a few cells across, so that their repetition periods are necessarily quite short. … The maximum repetition period for rule 90 is 2 (n - 1)/2 - 1 . For rule 30, the peak repetition periods are of order 2 0.63 n , while for rule 45, they are close to 2 n (for n = 29 , for example, the period is 463,347,935, which is 86% of the maximum possible).

Thus the patterns on page 189 can be formed from t -digit integers in base  - 1 containing only digits 0 and 1, as given by Table[FromDigits[IntegerDigits[s, 2, t],  - 1], {s, 0, 2 t -1}] In the particular case of base  - q with digits 0 through q 2 , it turns out that for sufficiently large t any complex integer can be represented, and will therefore be part of the pattern.

Block cellular automata With a rule of the form {{1, 1}  {1, 1}, {1, 0}  {1, 0}, {0, 1}  {0, 0}, {0, 0}  {0, 1}} the evolution of a block cellular automaton with blocks of size n can be implemented using BCAEvolveList[{n_Integer, rule_}, init_, t_] := FoldList[BCAStep[{n, rule}, #1, #2]&, init, Range[t]] /; Mod[Length[init], n]  0 BCAStep[{n_, rule_}, a_, d_] := RotateRight[ Flatten[Partition[RotateLeft[a, d], n]/.rule], d] Starting with a single black cell, none of the k = 2 , n = 2 block cellular automata generate anything beyond simple nested patterns. … For k = 2 , the number of rules that conserve the total number of black cells can be computed from q = Binomial[n, Range[0, n]] as Apply[Times, q q ] . … In general, a block cellular automaton is reversible only if its rule simply permutes the k n possible blocks.

(Note that to get only integer sequences such generating functions have to be specially chosen.) Sqrt[1 - 4 x]/2 yields a sequence with 1's at positions 2 m , as essentially obtained from the substitution system {2  {2, 1}, 1  {1, 0}, 0  {0, 0}} . … (This particular generating function satisfies the equation (1 + x) 3 f 2 - (1 + x) 2 f + x  0 .) (1 - 9 x) 1/3 yields almost the Cantor set sequence from page 83 .