Given two numbers x and y their product can be computed in base k by ( FromDigits does the carries) FromDigits[ListConvolve[IntegerDigits[x, k], IntegerDigits[y, k], {1, -1}, 0], k] For numbers with n digits direct evaluation of the convolution would take about n 2 steps. … 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. … Note that even though one may only want to find a single digit in m t , I know of no way to do this without essentially computing all the other digits in m t as well.

An example is the algorithm of Anatolii Karatsuba from 1961 for finding products of n -digit numbers (with n = 2 s ) by operating on their digits in the nested pattern of page 608 (see also page 1093 ) according to First[f[IntegerDigits[x, 2, n], IntegerDigits[y, 2, n], n/2]] f[x_, y_, n_] := If[n < 1, x y, g[Partition[x, n], Partition[y, n], n]] g[{x1_, x0_}, {y1_, y0_}, n_] := With[{z1 = f[x1, y1, n/2], z0 = f[x0, y0, n/2]}, z1 2 2n + (f[x0 + x1, y0 + y1, n/2] - z1 - z0)2 n + z0] Other examples include the fast Fourier transform (page 1074 ) and related algorithms for ListConvolve , the quicksort algorithm for Sort , and many algorithms in fields such as computational geometry.

A variety of atomic and other processes give pairs of photons that are forced to have total spin 0. … Now the expected value of the product of the two measured spin values is found just by averaging over ϕ as Integrate[f[ ϕ ] f[ θ - ϕ ], { ϕ , 0, 2 π }]/(2 π ) A version of Bell's inequalities is then that this integral can decrease with θ no faster than θ /(2 π ) - 1 —as achieved when f = Sign . … (In the standard formalism of quantum theory this is normally explained by saying that the two photons can only meaningfully be considered as part of a single "entangled" state.

But my guess is that its most important function is quite mundane: just as muscles build up lactic acid waste products, so also I suspect synapses in the brain build up waste products, and these can only safely be cleared out when the brain is not in normal use.

But in 3D, this probability (on a simple cubic lattice) drops to about 0.341, and in d dimensions the probability falls roughly like 1/(2d) . … To make a random walk on a lattice with k directions in two dimensions, one can set up e = Table[{Cos[2 π s/k], Sin[2 π s/k]}, {s, 0, k - 1}] then use FoldList[Plus, {0, 0}, Table[e 〚 Random[Integer, {1, k}] 〛 , {t}]] It turns out that on any regular lattice, in any number of dimensions, the average behavior of a random walk is always isotropic. As discussed in the note below, this can be viewed as a consequence of the fact that the probability distribution in a random walk depends only on Sum[Outer[Times, e 〚 s 〛 , e 〚 s 〛 ], {s, Length[e]}] and not on products of more of the e 〚 s 〛 .

f[n_] := n f[n - 1]; f[1] = 1 f[n_] := Product[i, {i, n}] f[n_] := Module[{t = 1}, Do[t = t i, {i, n}]; t] f[n_] := Module[{t = 1, i}, For[i = 1, i ≤ n, i++, t ⋆ = i]; t] f[n_] := Apply[Times, Range[n]] f[n_] := Fold[Times, 1, Range[n]] f[n_] := If[n  1, 1, n f[n - 1]] f[n_] := Fold[#2[#1] &, 1, Array[Function[t, # t] &, n]] f = If[#1  1, 1, #1 #0[#1 - 1]] &

Applying FoldList[Plus, 0, 2list - 1] to the whole sequence yields the pattern shown below. … This is similar to picture (c) on page 131 , and is a digit-by-digit version of FoldList[Plus, 0, Table[Apply[Plus, 2 Rest[IntegerDigits[i, 2]] - 1], {i, n}]] Note that although the picture above has a nested structure, the original concatenation sequences are not nested, and so cannot be generated by substitution systems. 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 basic idea is to encode the list of values of all the registers in the multiregister machine in the single number given by RMEncode[list_] := Product[Prime[j]^list 〚 j 〛 , {j, Length[list]}] and then to have this number be the value at appropriate steps of the first register in the 2-register machine. 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.

Patterns generated by rules of the type shown on the previous page , with a range of choices for the weights of cells at distances 2 and 3. Weights vary from -0.9 to 0 down the page for distance 2, and from -0.7 to 0.4 across the page for distance 3. … In the first case, cells at distances 2 and 3 only have an effect in the vertical direction; in the second case, they only have an effect in the horizontal direction.

History [of Pascal's triangle mod k ] Pascal's triangle probably dates from antiquity; it was known in China in the 1200s, and was discussed in some detail by Blaise Pascal in 1654, particularly in connection with probability theory.