The systematic increase is a consequence of the leading 1 in each concatenated sequence. Dropping this 1 yields the pattern below. … The element at position n in the first sequence discussed above can however be obtained in about Log[n] steps using ((IntegerDigits[#3 + Quotient[#1, #2], 2] 〚 Mod[#1, #2] + 1 〛 &)[n - (# - 2)2 # - 1 - 2, #, 2 # - 1 ]&)[NestWhile[# + 1&, 0, (# - 1)2 # + 1 < n &]] where the result of the NestWhile can be expressed as Ceiling[1 + ProductLog[1/2(n - 1)Log[2]]/Log[2]] Following work by Maxim Rytin in the late 1990s about k n+1 digits of a concatenation sequence can be found fairly efficiently from k/(k - 1) 2 - (k - 1) Sum[k (k s - 1) ((1 + s - s k)/(k - 1)) (1/((k - 1) (k s - 1) 2 ) - k/((k - 1) (k s + 1 - 1) 2 ) + 1/(k s + 1 - 1)), {s, n}] Concatenation sequences can also be generated by joining together digits from other representations of numbers; the picture below shows results for the Gray code representation from page 901 .

Fibonacci numbers The Fibonacci numbers Fibonacci[n] ( f[n] for short) can be generated by the recurrence relation f[n_] := f[n] = f[n-1] + f[n - 2] f[1] = f[2] = 1 The first few Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377. For large n the ratio f[n]/f[n - 1] approaches GoldenRatio or (1 + √ 5 )/2 ≃ 1.618 . Fibonacci[n] can be obtained in many ways: • (GoldenRatio n - (-GoldenRatio) -n )/ √ 5 • Round[GoldenRatio n / √ 5 ] • 2 1 - n Coefficient[(1 + √ 5 ) n , √ 5 ] • MatrixPower[{{1, 1}, {1, 0}}, n - 1] 〚 1, 1 〛 • Numerator[NestList[1/(1 + #)&, 1, n]] • Coefficient[Series[1/(1 - t - t 2 ), {t, 0, n}], t n - 1 ] • Sum[Binomial[n - i - 1, i], {i, 0, (n - 1)/2}] • 2 n - 2 - Count[IntegerDigits[Range[0, 2 n - 2 ], 2], {___, 1, 1, ___}] A fast method for evaluating Fibonacci[n] is First[Fold[f, {1, 0, -1}, Rest[IntegerDigits[n, 2]]]] f[{a_, b_, s_}, 0] = {a (a + 2b), s + a (2a - b), 1} f[{a_, b_, s_}, 1] = {-s + (a + b) (a + 2b), a (a + 2b), -1} Fibonacci numbers appear to have first arisen in perhaps 200 BC in work by Pingala on enumerating possible patterns of poetry formed from syllables of two lengths.

For sequences involving only two distinct integers flat spectra are rare; with ± 1 those equivalent to {1, 1, 1, -1} seem to be the only examples. ( {r 2 , r s, s 2 , -r s} works for any r and s , as do all lists obtained working modulo x n - 1 from p[x]/p[1/x] where p[x] is any invertible polynomial.) … Sequences of 0's and 1's that have the same property are {1, 0, 1, 0} , {1, 0, 0, 1, 0, 0, 1, 0, 0} or in general Flatten[Table[{1, Table[0, {n - 1}]}, {n}]] . If -1 is allowed, additional sequences such as {0, 1, 0, -1, 0, -1, 0, 1} are also possible.

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}} . Sqrt[(1 - 3 x)/(1 + x)]/2 yields sequence (a) on page 84 . (1 + Sqrt[(1 - 3 x)/(1 + x)])/(2(1 + x)) (see page 890 ) yields the Thue–Morse sequence. … For the Thue–Morse sequence the result is 1/2 (-1) n + ((-3) n √ π Hypergeometric2F1[3/2, -n, 3/2 - n, -(1/3)])/(4 n!

MapIndexed[ #1  First[#2] &, Union[Map[# 〚 1, 1 〛 &, #]]] &[ With[{b = Ceiling[Log[2, k]] - 1}, Flatten[Table[ {Table[{Table[{{m, i, n, d}, c}  {{m, Mod[i, 2 n - 1 ], n - 1, d}, Quotient[i, 2 n - 1 ], 1}, {n, 2, b}, {i, 0, 2 n - 1}], Table[{ {m, i, 1, d}, c}  {{m, -1, 1, d}, i, d}, {i, 0, 1}], Table[ {{m, -1, n, d}, c}  {{m, -1, n + 1, d}, c, d}, {n, b - 1}], {{m, -1, b, d}, c}  {{0, 0, m}, c, d}}, {d, -1, 1, 2}], Table[{{i, n, m}, c}  {{ i + 2 n c, n + 1, m}, c, -1}, {n, 0, b - 1}, {i, 0, 2 n - 1}], With[{r = 2 b }, Table[ If[i + r c ≥ k, {}, Cases[rule, ({m, i + r c}  {x_, y_, z_})  {{i, b, m}, c}  {{x, Mod[y, r], b, z}, Quotient[y, r], 1})]], {i, 0, r - 1}]]}, {m, s}, {c, 0, 1}]]]] Some of these states are usually unnecessary, and in the main text such states have been pruned.

Background [in rule 110] At every step the background pattern in rule 110 consists of repetitions of the block b = {1,0,0,1,1,0,1,1,1,1,1,0,0,0} , as shown in the picture below. On step t the color of a cell at position x is given by b 〚 Mod[x + 4 t, 14] + 1 〛 .

The program in the multiregister machine can be converted to a program for the 2-register machine according to RMToRM2[prog_] := Module[{segs, adrs}, segs = MapIndexed[seg, prog]; adrs = FoldList[Plus, 1, Map[Length, segs]]; MapIndexed[#1 /. {ds[r_, s_]  d[r, adrs 〚 s 〛 ], dr[r_, j_]  d[r, j + First[#2]]} &, Flatten[segs]]] seg[i[r_], {a_}] := With[{p = Prime[r]}, Flatten[{Table[i[2], {p}], dr[1, -p], i[1], dr[2, -1], Table[dr[1, 1], {p + 1}]}]] seg[d[r_, n_], {a_}] := With[{p = Prime[r]}, Flatten[{i[2], dr[ 1, 5], i[1], dr[2, -1], dr[1, 1], ds[1, n], Table[{If[m  p - 1, ds[1, a], dr[1, 3p + 2 - m]], Table[i[1], {p}], dr[2, -p], Table[dr[1, 1], {2p - m - 1}], ds[1, a + 1]}, {m, p - 1}]}]] The initial conditions for the 2-register machine are given by {1, {RMEncode[list], 0}} and the results corresponding to each step in the evolution of the multiregister machine appear whenever register 2 in the 2-register machine is incremented from 0.

For case (c) above, m = {{1, 1}, {1, 0}} . … For the rule {0  {0, 1}, 1  {1}} , m = {{1, 1}, {0, 1}} , and the number of elements at step t starting with {0} is just t . For {0  {0, 1}, 1  {1, 2}, 2  {2}} , m = {{1, 1, 0}, {0, 1, 1}, {0, 0, 1}} , and the number of elements starting with {0} is (t 2 - t + 2)/2 .

The first m rules (which yield far more than m elements of the original sequence) are obtained for any h that is not a rational number from the continued fraction form (see page 914 ) of h by Map[(({0  Join[#, {1}], 1  Join[#, {1, 0}]} &)[Table[0, {# - 1}]]) &, Reverse[Rest[ContinuedFraction[h, m]]]] Given these rules, the original sequence is given by Floor[h] + Fold[Flatten[#1 /. #2] &, {0}, rules] If h is the solution to a quadratic equation, then the continued fraction form is repetitive, and so there are a limited number of different substitution rules. … For h = GoldenRatio the substitution system is {0  {1}, 1  {1, 0}} (see page 890 ), for h = √ 2 it is {0  {0, 1}, 1  {0, 1, 0}} (see page 892 ) and for h = √ 3 it is {0  {1, 1, 0}, 1  {1, 1, 0, 1}} . (The presence of nested structure is particularly evident in FoldList[Plus, 0, Table[Mod[h n, 1] - 1/2, {n, max}]] .)

Thus for example {(0 | 1) ...} corresponds to all possible sequences of 0 's and 1 's, while {1, 1, (1) ..., 0, (0) ...} ... corresponds to the sequences that can occur after 2 steps in rule 126 and {(0) ..., 1, {0, (0) ..., 1, 1} | {1, (1) ..., 0}} ... to those that can occur after 2 steps in rule 110 (see page 279 ).