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[kt, n] after t steps. If k and n have no factors in common, there will be a t for which Mod[kt, 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 ks, 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.



Image Source Notebooks:

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