In case (c), the following gives a list of the numbers of nodes generated up to step t : FoldList[Plus, 1, Join[{1, 4, 12, 10, -20, 6, 4}, Map[d, IntegerDigits[Range[4, t - 5], 2]]]] d[{___, 1}] = 1 d[{1, p : 0 .., 0}] := -Apply[Plus, 4 Range[Length[{p}]] - 1] + 6 d[{__, 1, p : 0 .., 0}] := d[{1, p, 0}] - 7 d[{___, p : 1 .., q : 0 ..., 1, 0}] := 4 Length[{p}] + 3 Length[{q}] + 2 d[{___, p : 1 .., 1, 0}] := 4 Length[{p}] + 2

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 ] . The number of these rules that are also reversible is Apply[Times, q!]

For any input x one can test whether the machine will ever halt using u[{Reverse[IntegerDigits[x, 2]], 0}] u[list_] := v[Split[Flatten[list]]] v[{a_, b_: {}, c_: {}, d_: {}, e_: {}, f_: {}, g___}] := Which[a == {1} || First[a]  0, True, c  {}, False, EvenQ[Length[b]], u[{a, 1 - b, c, d, e, f, g}], EvenQ[Length[c]], u[{a, 1 - b, c, 1, Rest[d], e, f, g, 0}], e  {} || Length[d] ≥ Length[b] + Length[a] - 2, True, EvenQ[Length[e]], u[{a, b , c, d, f, g}], True, u[{a, 1 - b, c, 1 - d, e, 1, Rest[f], g, 0}]] This test takes at most n/3 recursive steps, even though the original machine can take of order n 2 steps to halt.

In Mathematica functions like TrueQ and IntegerQ are set up always to yield True or False —but just by looking at the explicit structure of a symbolic expression.

But given t steps in this sequence as a list of 0's and 1's, the following function will reconstruct the rightmost t digits in the starting value of n : IntegerDigits[First[Fold[{Mod[If[OddQ[#2], 2 First[#1] - 1, 2 First[#1] PowerMod[5, -1, Last[#1]]], Last[#1]], 2 Last[#1]} &, {0, 2}, Reverse[list]]], 2, Length[list]]

EvenQ] := Partition[ Fold[Insert[#1, #2, Random[Integer, Length[#1]] + 1] &, {}, Floor[Range[1, n + 2/3, 1/3]]], 2] Networks obtained in this way are usually connected, but will almost always contain self-loops and multiple edges.

The inverse rule, corresponding to multiplication by 1/m , can be obtained by applying the rule for multiplication by the integer k q /m , then shifting right by q positions.

The rules for the multiway system can then be given for example as {"AAB"  "BB", "BA"  "ABB"} The evolution of the system is given by the functions MWStep[rule_List, slist_List] := Union[Flatten[ Map[Function[s, Map[MWStep1[#, s] &, rule]], slist]]] MWStep1[p_String  q_String, s_String] := Map[StringReplacePart[s, q, #] &, StringPosition[s, p]] MWEvolveList[rule_, init_List, t_Integer] := NestList[MWStep[rule, #] &, init, t] An alternative approach uses lists instead of strings, and in effect works by tracing the internal steps that Mathematica goes through in trying out possible matchings.

Factoring integers The difficulty of factoring is presumably related to the irregularity of the pattern of divisors shown on page 909 . … Typical running times for FactorInteger[n] in Mathematica 4 are shown below for the first 1000 numbers with each of 15 through 30 digits. … Nevertheless, to test whether a number is prime ( PrimeQ ) it is known that only a few more than Log[n] steps suffice.

The main such systems and their dates of earliest known reasonably formalized use have been (see also page 901 ): positive integers (before 10,000 BC), rationals (3000 BC), square roots (2000 BC), other roots (1800 BC), all integers (600 AD, 1600s), decimals (950 AD), complex numbers (1500s, 1800s), polynomials (1591), infinitesimals (1635), algebraic numbers (1744), quaternions (1843), Grassmann algebra (1844), ideals (1844, 1871), octonions (~1845), Boolean algebra (1847), fields (1850s, 1871), matrices (1858), associative algebras (1870), axiomatic real numbers (1872), vectors (1881), transfinite ordinals (1883), transfinite cardinals (1883), operator calculus (1880s), Boolean algebras (1890), algebraic number fields (1893), rings (1897), p -adic numbers (1897), non-Archimedean fields (1899), q -numbers (1926), non-standard integers (1930s), non-standard reals (hyperreals) (1960), interval arithmetic (1968), fuzzy arithmetic (1970s), surreal numbers (1970s).