The digits of 1/n in base b repeat with period MultiplicativeOrder[b, FixedPoint[#/GCD[#, b] &, n]] which is equal to MultiplicativeOrder[b, n] for prime n , and is at most n - 1 .

Cyclic multiplication With multiplication by k at each step the dot will be at position Mod[k t , n] after t steps. … 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. … In general, the dot will visit position m = k^IntegerExponent[n, k] every MultiplicativeOrder[k, n/m] steps.

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 .

Ordering of [mathematical] constructs One can deduce some kind of ordering among standard mathematical constructs by seeing how difficult they are to implement in various systems—such as cellular automata, Turing machines and Diophantine equations. My experience has usually been that addition is easiest, followed by multiplication, powers, Fibonacci numbers, perfect numbers and then primes. And perhaps this is similar to the order in which these constructs appeared in the early history of mathematics.

In the system x  Mod[2x, n] from page 257 , the repetition period MultiplicativeOrder[2, n] probably cannot always be computed in any polynomial of Log[n] steps, since otherwise FactorInteger[n] could also be computed in about this number of steps. … But even with an additive rule and nested behavior, the period depends on quantities like MultiplicativeOrder[2, n] , which probably take more like n steps to evaluate.

The bottom plot gives the repetition period for this system as a function of its size; for odd n this period is equal to MultiplicativeOrder[2, n] .

Using the result that (1 + x 2 m )  (1 + x) 2 m modulo 2 for any m , one then finds that the repetition period always divides the quantity p[n]=2^MultiplicativeOrder[2, n] - 1 , which in turn is at most 2 n-1 -1 . … And now the repetition period for odd n divides q[n]=2^MultiplicativeOrder[2, n, {1,-1}] - 1 The exponent here always lies between Log[k, n] and (n-1)/2 , with the upper bound being attained only if n is prime.

Fourier[data] can be thought of as multiplication by the n × n matrix Array[Exp[2 π  #1 #2/n] &, {n, n}, 0] . Applying BitReverseOrder to this matrix yields a matrix which has an essentially nested form, and for size n = 2 s can be obtained from Nest[With[{c = BitReverseOrder[Range[0, Length[#] - 1]/ Length[#]]}, Flatten2D[MapIndexed[#1 {{1, 1}, {1, -1} (-1)^c 〚 Last[#2] 〛 } &, #, {2}]]] &, {{1}}, s] Using this structure, one obtains the so-called fast Fourier transform which operates in n Log[n] steps and is given by With[{n = Length[data]}, Fold[Flatten[Map[With[ {k = Length[#]/2}, {{1, 1}, {1, -1}} . {Take[#, k], Drop[ #, k](-1)^(Range[0, k - 1]/k)}] &, Partition[##]]] &, BitReverseOrder[data], 2^Range[Log[2, n]]]/ √ n ] (See also page 1080 .)

.); Toda lattice (1967) ( Sech ); six-vertex spin model (1967) ( Sinh integrals); Calogero–Moser model (1971) ( Hypergeometric1F1 ); Yang–Mills instantons (1975) (rational functions); hard-hexagon spin model (1979) ( EllipticTheta ); additive cellular automata (1984) ( MultiplicativeOrder ); Seiberg–Witten supersymmetric theory (1994) ( Hypergeometric2F1 ).

The evolution of such a quantum system can then formally be represented by successive multiplication of the vector of amplitudes by appropriate 2 n × 2 n unitary matrices. In a classical system like a cellular automaton with n cells a probabilistic ensemble of states can similarly be described by a vector of 2 n probabilities p i —now satisfying Sum[p i , {i, 2 n }]  1 , and evolving by multiplication with 2 n × 2 n matrices having a single 1 in each row. … As mentioned in the note above, it becomes straightforward to factor m if one can get the values of MultiplicativeOrder[a, m] .