Notes

Chapter 6: Starting from Randomness

Section 4: Systems of Limited Size and Class 2 Behavior


Cyclic multiplication

With multiplication by k at each step the dot will be at position Mod[k^t, n] after t steps. If k and n have no factors in common, there will be a t for which Mod[k^t, n] == 1, so that the dot returns to position 1. The smallest such t is given by MultiplicativeOrder[k, n], which always divides EulerPhi[n] (see page 1093), and has a value between Log[k, n] and n-1, with the upper limit being attained only if n is prime. (This value is related to the repetition period for the digit sequence of 1/n in base k, as discussed on page 912). When GCD[k, n]==1 the dot can never visit position 0. But if n==k^s, the dot reaches 0 after s steps, and then stays there. In general, the dot will visit position m=k^IntegerExponent[n,k] every MultiplicativeOrder[k, n/m] steps.


From Stephen Wolfram: A New Kind of Science [citation]