# Search NKS | Online

11 - 20 of 115 for IntegerDigits

Concatenation sequences
One can consider forming sequences by concatenating digits of successive integers in base k , as in Flatten[Table[IntegerDigits[i, k], {i, n}]] . … 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 .

Computing powers [of numbers]
The method of repeated squaring (also known as the binary power method, Russian peasant method and Pingala's method) computes the quantity m t by performing about Log[t] multiplications and building up the sequence
FoldList[#1 2 m #2 &, 1, IntegerDigits[t, 2]]
(related to the Horner form for the base 2 representation of t ). 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. … 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.

Digit reversal
Sequences of the form
Table[FromDigits[ Reverse[IntegerDigits[n, k, m]], k], {n, 0, k m - 1}]
shown below appear in algorithms such as the fast Fourier transform and, with different values of k for different coordinates, in certain quasi-Monte Carlo schemes.

Implementation [of 2D cellular automata]
An n × n array of white squares with a single black square in the middle can be generated by
PadLeft[{{1}}, {n, n}, 0, Floor[{n, n}/2]]
For the 5-neighbor rules introduced on page 170 each step can be implemented by
CAStep[rule_, a_] := Map[rule 〚 10 - # 〛 &, ListConvolve[{{0, 2, 0}, {2, 1, 2}, {0, 2, 0}}, a, 2], {2}]
where rule is obtained from the code number by IntegerDigits[code, 2, 10] .
For the 9-neighbor rules introduced on page 177
CAStep[rule_, a_] := Map[rule 〚 18 - # 〛 &, ListConvolve[{{2, 2, 2}, {2, 1, 2}, {2, 2, 2}}, a, 2], {2}]
where rule is given by IntegerDigits[code, 2, 18] .
In d dimensions with k colors, 5-neighbor rules generalize to (2d + 1) -neighbor rules, with
CAStep[{rule_, d_}, a_] := Map[rule 〚 -1 - # 〛 &, a + k AxesTotal[a, d], {d}]
AxesTotal[a_, d_] := Apply[Plus, Map[RotateLeft[a, #] + RotateRight[a, #]&, IdentityMatrix[d]]]
with rule given by IntegerDigits[code, k, k(2d(k - 1) + 1)] .
9-neighbor rules generalize to 3 d -neighbor rules, with
CAStep[{rule_, d_}, a_] := Map[rule 〚 -1 - # 〛 &, a + k FullTotal[a, d], {d}]
FullTotal[a_, d_] := Array[RotateLeft[a, {##}] &, Table[3, {d}], -1, Plus] - a
with rule given by IntegerDigits[code, k, k((3 d - 1)(k - 1) + 1)] .

Implementation of digit sequences
A whole number n can be converted to a sequence of digits in base k using IntegerDigits[n,k] or (see also page 1094 )
Reverse[Mod[NestWhileList[Floor[#/k] &, n, # ≥ k &], k]]
and from a sequence of digits using FromDigits[list,k] or
Fold[k #1 + #2 &, 0, list]
For a number x between 0 and 1, the first m digits in its digit sequence in base k are given by RealDigits[x, k, m] or
Floor[k NestList[Mod[k #, 1]&, x, m - 1]]
and from these digits one can reconstruct an approximation to the number using FromDigits[{list, 0}, k] or
Fold[#1/k + #2 &, 0, Reverse[list]]/k

The number of steps for which a cell at position n will survive can be computed as
Module[{q = n + k - 1, s = 1}, While[Mod[q, k] ≠ 0, q = Ceiling[(k - 1)q/k]; s++]; s]
If a cell is going to survive for s steps, then it turns out that this can be determined by looking at the last s digits in the base k representation of its position. For k = 2 , a cell survives for s steps if these digits are all 0 (so that s IntegerExponent[n, k] ). … The solution is Fold[Mod[#1 + k, #2, 1]&, 0, Range[n]] , or FromDigits[RotateLeft[IntegerDigits[n, 2]], 2] for k = 2 .

Properties of [recursive] sequences
Sequence (d) is given by
f[n_] := (n + g[IntegerDigits[n, 2]])/2
g[{1 ..}] = 1; g[{1, 0 ..}] = 0
g[{1, s__}] := 1 + g[IntegerDigits[FromDigits[{s}, 2] + 1, 2]]
The list of elements in the sequence up to value m is given by
Flatten[Table[Table[n, {IntegerExponent[n, 2] + 1}], {n, m}]]
The differences between the first 2 (2 k -1) of these elements is
Nest[Replace[#, {x___} {x, 1, x, 0}]&, {}, k]
The largest n for which f[n] m is given by 2m + 1 - DigitCount[m, 2, 1] or IntegerExponent[(2m)!… Hump m in the picture of sequence (c) shown is given by
FoldList[Plus, 0, Flatten[Nest[Delete[NestList[Rest, #, Length[#] - 1], 2]&, Append[Table[1, {m}], 0], m]] - 1/2]
The first 2 m elements in the sequence can also be generated in terms of reordered base 2 digit sequences by
FoldList[Plus, 1, Map[Last[Last[#]]&, Sort[Table[{Length[#], Apply[Plus, #], 1 - #}& [ IntegerDigits[i, 2]], {i, 2 m }]]]]
Note that the positive and negative fluctuations in sequence (f) are not completely random: although the probability for individual fluctuations in each direction seems to be the same, the probability for two positive fluctuations in a row is smaller than for two negative fluctuations in a row.

[Subset of] elementary rules
The examples shown have rule numbers n for which IntegerDigits[n, 2, 8] matches {_, i_, _, j_, i_, _, j_, 0} .

Reversible mobile automata can for instance be constructed using
Table[(IntegerDigits[i, 2, 3] If[First[#] 0, {#, -1}, {Reverse[#], 1}]&)[IntegerDigits[perm 〚 i 〛 , 2, 3]], {i, 8}]
where perm is an element of Permutations[Range[8]] .

Numbering scheme [for 2D constraints]
The constraint numbered n allows the templates at Position[IntegerDigits[n, 2, 32], 1] in the list below.