Search NKS | Online
41 - 50 of 115 for IntegerDigits
Cases like (c) and (d) show nested behavior reminiscent of a counter which generates digit sequences of successive integers.
Connection [of 2D substitution systems] with digit sequences
Just as in the 1D case discussed on page 891 , the color of a cell at position {i, j} in a 2D substitution system can be determined using a finite automaton from the digit sequences of the numbers i and j . At step n , the complete array of cells is
Table[If[FreeQ[Transpose[IntegerDigits[{i, j}, k, n]], form], 1, 0], {i, 0, k n - 1}, {j, 0, k n - 1}]
where for the pattern on page 187 , k = 2 and form = {0, 1} . … Note that the excluded pairs of digits are in exact correspondence with the positions of which squares are 0 in the underlying rules for the substitution systems.
Digit sequence encryption
One can consider using as encrypting sequences the digit sequences of numbers obtained from standard mathematical functions. … Thus, for example, given the digit sequence of √ s one can retrieve the key s just by squaring the number obtained from early digits in the sequence. Whenever a number x is known to satisfy Sum[a[i] f[i][x], {i, n}] 0 with fixed f[i] one can take the early digits of x and use LatticeReduce to find integer solutions for the a[i] .
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.
Implementation of general cellular automata
With k colors and r neighbors on each side, a single step in the evolution of a general cellular automaton is given by
CAStep[CARule[rule_List, k_, r_], a_List] := rule 〚 -1 - ListConvolve[k^Range[0, 2r], a, r + 1] 〛
where rule is obtained from a rule number num by IntegerDigits[num, k, k 2r + 1 ] .
Numbering scheme [for Turing machines]
One can number Turing machines and get their rules using
Flatten[MapIndexed[{1, -1} #2 + {0, k} {1, 1, 2} Mod[Quotient[#1, {2k, 2, 1}], {s, k, 2}] + {1, 0, -1} &, Partition[IntegerDigits[n, 2 s k, s k], k], {2}]]
The examples on page 79 have numbers 3024, 982, 925, 1971, 2506 and 1953.
Specially constructed transcendental numbers
Numbers known to be transcendental include ones whose digit sequences contain 1's only at positions n! … Concatenation sequences, as well as generalizations formed by concatenating values of polynomials at successive integer points, are also known to yield numbers that are transcendental.
Repetition in numbers
A common source of repetition in systems involving numbers is the almost trivial fact that in a sequence of successive integers there is a repetitive pattern of cases at which a particular divisor occurs. Other examples include the repetitive structure of digits in rational numbers (see page 138 ) and continued fraction terms in square roots (see page 144 ).
In each case, the digit sequence of the number obtained at each step is shown in base 2. Multiplication by 2 turns out to correspond just to shifting all digits in base 2 one position to the left, so that the overall pattern produced in this case is very simple. … Note that in these pictures the complete numbers obtained at each step correspond respectively to the successive integer powers of 2 and of 3.
Particularly dramatic are the concatenation systems discussed on page 913 , as well as successive rows in nested patterns such as Flatten[IntegerDigits[NestList[BitXor[#, 2 #] &, 1, 500], 2]] and sequences based on numbers such as Flatten[Table[If[GCD[i, j] 0, 1, 0], {i, 1000}, {j, i}]] (see page 613 ).