Search NKS | Online
11 - 20 of 22 for IntegerExponent
![](/common/images/search/spacer.gif)
In general, the dot will visit position m = k^IntegerExponent[n, k] every MultiplicativeOrder[k, n/m] steps.
[No text on this page]
Universality in arithmetic, illustrated by an integer equation whose solutions in effect emulate the rule 110 universal cellular automaton from Chapter 11 . … Note that the equation shown is a so-called exponential Diophantine one, in which some variables appear in exponents.
This is nonzero when all prime factors of n of the form 4k + 3 appear with even exponents. … Note that the total number of integers less than n which can be expressed as a sum of three squares increases roughly like 5n/6 , with fluctuations related to IntegerDigits[n, 4] . … The total number of ways that integers less than n can be expressed as a sum of d squares is equal to the number of integer lattice points that lie inside a sphere of radius Sqrt[n] in d -dimensional space.
For all initial conditions this depth seems at first to increase linearly, then to decrease in a nested way according to
FoldList[Plus, 0, Flatten[Table[ {1, 1, Table[-1, {IntegerExponent[i, 2] + 1}]}, {i, m}]]]
This quantity alternates between value 1 at position 2 j and value j at position 2 j - j + 1 .
An alternative formulation is to ask whether for all n
FixedPoint[(3#/2^IntegerExponent[#, 2] + 1)/2 &, n] 2
With the rule n If[EvenQ[n], 5n/2, (n + 1)/2] used in the main text, the sequence produced repeats if n ever reaches 2, 4 or 40 (and possibly higher numbers). … Starting with n = 6 , the effective exponents for t = 10^Range[6] are {39.6, 245.1, 1202.8, 9250.7, 98269.8, 1002020.4} .
And the reason is that one can generate the elements in it by effectively maintaining a copy of the Turing machine for each possible initial condition, then following a procedure where for example at step n one updates the one for initial condition IntegerExponent[n, 2] , and watches to see if it halts.
The n th element is given by Mod[IntegerExponent[n, 2], 2] .
So for example the equation a 2 + b 2 0 has solutions that are exactly those integers that satisfy the relation a 0 ∧ b 0 . … In the universal equation in the main text variables appear in exponents. One can reduce such an exponential equation to a pure polynomial equation by encoding powers using integer equations.
The number of steps before a machine with given rule halts can be computed from (see page 888 )
Module[{s = 1, a, i = 1, d}, a[_] = 0; MapIndexed[a[#2 〚 1 〛 ] = #1 &, Reverse[IntegerDigits[x, 2]]]; Do[{s, a[i], d} = {s, a[i]} /. rule; i -= d; If[i 0, Return[t]], {t, tmax}]]
Of the 4096 Turing machines with s = 2 , k = 2 , 748 never halt, 3348 sometimes halt and 1683 always halt. … Machine 1447 (example (e)) computes the function which takes the digit sequence of x and replaces its first 3 + IntegerExponent[x + 1, 2] 0's by 1's.
(d) (Period-doubling sequence) The spectrum is (2 # - (-1) # &)[1 + IntegerExponent[n, 2]] , almost like the markings on a base 2 ruler.
![](/common/images/search/spacer.gif)