Search NKS | Online
1 - 10 of 22 for IntegerExponent
![](/common/images/search/spacer.gif)
When n is even, the structure is a balanced tree of depth 2^IntegerExponent[n, 2] and degree 2 for rule 60, and depth 2^IntegerExponent[n/2, 2] and degree 4 for rule 90. The total fraction of states on cycles is in both cases 2^-2^IntegerExponent[n, 2] .
Other integer functions
IntegerExponent[n, k] gives nested behavior as for decimation systems on page 909 , while MultiplicativeOrder[k, n] and EulerPhi[n] yield more complicated behavior, as shown on pages 257 and 1093 .
Formulas for DigitCount[n, 2, 1] include n - IntegerExponent[n!… Straightforward generalizations of DigitCount can be defined for integer and non-integer bases and by looking not only at the total number of digits but also at correlations between digits.
The output f[x] in such cases is always 2 u - 1 where
u = Nest[(13 + (6# + 8)(5/2)^ IntegerExponent[6# + 8, 2])/6 &, 1, s + 1]
One then finds that 6u + 8 has the form Nest[If[EvenQ[#], 5#/2, # + 21]&, 14, m] for some m , suggesting a connection with the number theory systems of page 122 . The corresponding halting time t[x] is Last[Nest[h, {8, 4s + 24 }, s]] - 1 with
h[{i_, j_}] := With[{e = IntegerExponent[3i + 4, 2]}, {13/6 + (i + 4/3)(5/2) e + 1 , ((154 + 75(i + 4/3)(5/2) e ) 2 - 16321 - 7860i - 900i 2 + 3360e)/3780 + j}]
For s > 3 it then turns out that f[x] is extremely close to 3560523 (5/2) r , and t[x] to 18865098979373 (5/2) 2r , for some integer r .
… But if IntegerDigits[x, 2] involves no consecutive 0's then for example f[x] can be obtained from
2^(b[Join[{1, 1}, #], Length[#]] &)[IntegerDigits[x, 2]] - 1
a[{l_, _}, r_] := ({l + (5r - 3#)/2, #} &)[Mod[r, 2]]
a[{l_, 0}, 0] := {l + 1, 0}
a[{l_, 1}, 0] := ({(13 + #(5/2)^IntegerExponent[#, 2])/6, 0} &[6l + 2]
b[list_, i_] := First[Fold[a, {Apply[Plus, Drop[list, -i]], 0}, Apply[Plus, Split[Take[list, -i], #1 #2 ≠ 0 &], 1]]]
(The corresponding expression for t[x] is more complicated.)
The number of cells that are not white on row t in this case is given by Apply[Times, 1 + IntegerDigits[t, k]] . … A related result is that IntegerExponent[Binomial[t, n], k] is given by the number of borrows in the base k subtraction of n from t . 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.
In general, if a period m is possible then so must all periods n for which p = {m, n} satisfies
OrderedQ[Transpose[If[MemberQ[p/#, 1], Map[Reverse, {p/#, #}], {#, p/#}]] &[2^IntegerExponent[p, 2]]]
Extensions of this to other types of systems seem difficult to find, but it is conceivable that when viewed as continuous mappings on a Cantor set (see page 869 ) at least some cellular automata might exhibit similar properties.
Corresponding to the result on page 870 for rule 90, the number of black cells at row t in the pattern from rule 150 is given by
Apply[Times, Map[(2 # + 2 - (-1) # + 2 )/3 &, Cases[Split[IntegerDigits[t, 2]], k:{1 ..} Length[k]]]]
There are a total of 2 m Fibonacci[m+2] black cells in the pattern obtained up to step 2 m , implying fractal dimension Log[2, 1 + Sqrt[5]] . … The value at step t in the column immediately adjacent to the center is the nested sequence discussed on page 892 and given by Mod[IntegerExponent[t, 2], 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.
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 .
The result turns out to be given by 2 IntegerExponent[x + 1, 2] + 3 , which has a maximum of 2n+3 , where n is the length of the digit sequence of x , or Floor[Log[2, x]] .
![](/common/images/search/spacer.gif)