Mod[Binomial[t, n], k] is given for prime k by With[{d = Ceiling[Log[k, Max[t, n] + 1]]}, Mod[Apply[Times, Apply[Binomial, Transpose[ {IntegerDigits[t, k, d] , IntegerDigits[n, k, d] }], {1}]], k]] The patterns obtained for any k are nested.

There are Ceiling[a/2] + Ceiling[2 a/3] - (a + 1) solutions, the one with smallest x being {Mod[2 a + 2, 3] + 1, 2 Floor[(2a + 2)/3] - (a + 2)} .

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]]

Closely related is the total probability for each form of behavior, given for example by Sum[2^-(Ceiling[Log[2, i]]) h[i], {i, ∞ }] .

The smallest examples that show other behavior are: • r[z, r[s, s]] , which is 1/2#(# + 1)& , with quadratic growth • r[z, r[s, c[s, s]]] , which is 2 # + 1 - # - 2 & , with exponential growth • r[z, r[s, p[2]]] , which is 2^Ceiling[Log[2, # + 2]] - # - 2 & , which shows very simple nesting • r[z, r[c[s, z], z]] , which is Mod[#, 2]& , with repetitive behavior • r[z, r[s, r[s, s]]] which is Fold[1/2#1(# + 1) + #2 &, 0, Range[#]]& , growing like 2 2 x . r[z, r[s, r[s, r[s, p[2]]]]] is the first function to show significantly more complex behavior, and indeed as the picture below indicates, it already shows remarkable randomness. From its definition, the function can be written as Fold[Fold[2^Ceiling[Log[2, Ceiling[(#1 + 2)/(#2 + 2)]]] (#2 + 2) - 2 - #1 &, #2, Range[#1]] &, 0, Range[#]]& Its first zeros are at {4, 126, 813, 966, 1166, 1177, 1666, 1897} .

However, the straightforward method for converting a t -digit number x to base k takes about t divisions, though this can be reduced to around Log[t] by using a recursive method such as FixedPoint[Flatten[Map[If[# < k, #, With[ {e = Ceiling[Log[k, #]/2]}, {Quotient[#, k e ], With[ {s = Mod[#, k e ]}, If[s  0, Table[0, {e}], {Table[0, {e - Floor[Log[k, s]] - 1}], s}]]}]] &, #]] &, {x}] The pictures below show stages in the computation of 3 20 (a) by a power tree in base 2 and (b) by conversion from base 3.

The first one on the bottom (with 63 comparisons) has a nested structure and uses the method invented by Kenneth Batcher in 1964: Flatten[Reverse[Flatten[With[{m = Ceiling[Log[2, n]] - 1}, Table[With[{d = If[i  m, 2 t , 2 i + 1 - 2 t ]}, Map[ {0, d} + # &, Select[Range[n - d], BitAnd[# - 1, 2 t ]  If[i  m, 0, 2 t ] &]]], {t, 0, m}, {i, t, m}]], 1]], 1] The second one on the bottom also uses 63 comparisons, while the last one is the smallest known for n = 16 : it uses 60 comparisons and was invented by Milton Green in 1969.

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 .

The maximum number of distinct nodes at any level in the tree has large fluctuations but its peaks seem to increase roughly linearly for all the rules on this page (in the Fibonacci case it is Ceiling[n/2] ).

For s[s][k][s[s[s][k]]][k] (case (k)) the size at step t - 7 is given by h[1] = h[2] = h[3] = 12 h[t_] := If[Mod[t, 4]  2, 2, 1] (h[Ceiling[t/2] - 1] + t) + {3, 5, -7, -1} 〚 Mod[t, 4] + 1 〛 Examples with similar behavior are s[s[s][k]][s][s[s][k]] , s[s[s]][s][s[s][k]][k] and s[s[s][s]][s][s[s][k]] .