(After t steps the dot is thus at position Mod[2 t , n] in a size n system.)

From various number-theoretical results many relations can readily be encoded as integer equations: (a  0 ∨ b  0) ↔ a b  0 (a  0 ∧ b  0) ↔ a + b  0 a < b ↔ b  a + c + 1 a  Mod[b, c] ↔ (b  a + c d ∧ a < c) a  Quotient[b, c] ↔ (b  a c + d ∧ d < c) a  Binomial[b, c] ↔ With[{n = 2 b + 1}, (n + 1) b  n c (a + d n) + e ∧ e < n c ∧ a < n] a  b! … , a]  1 ∧ a > 1) a  BitAnd[c, d] ∧ b  BitOr[c, d] ↔ ( σ [c, a] ∧ σ [d, a] ∧ σ [b, c] ∧ σ [b, d] ∧ a + b  c + d)/. σ [x_, y_]  Mod[Binomial[x, y], 2]  1 where the last encoding uses the result on page 608 . … The simplest known way of doing this (see note below ) involves a degree 8 equation with 60 variables: a  b c ↔ α [d, 4 + b e, 1 + z] ∧ α [f, e, 1 + z] ∧ a  Quotient[d, f] ∧ α [g, 4 + b, 1 + z] ∧ e  16 g(1 + z) λ [a_, b_, c_] := Module[{x}, 2 a + x 1  c ∧ (Mod[b - a, c]  0 ∨ Mod[b + a, c]  0)] α [a_, b_, c_] := Module[{x}, x 1 2 - b x 1 x 2 + x 2 2  1 ∧ x 3 2 - b x 3 x 4 + x 4 2  1 ∧ 1 + x 4 + x 5  x 3 ∧ Mod[x 3 , x 1 2 ]  0 ∧ 2x 4 + x 7  b x 3 ∧ Mod[-b + x 8 , x 7 ]  0 ∧ Mod[-2 + x 8 , x 1 ]  0 ∧ x 8 - x 11  3 ∧ x 12 2 - x 8 x 12 x 13 + x 13 2  1 ∧ 1 + 2 a + x 14  x 1 ∧ λ [a, x 12 , x 7 ] ∧ λ [c, x 12 , x 1 ]] (This roughly uses the idea that solutions to Pell equations grow exponentially, so that for example x 2  2y 2 + 1 has solutions With[{u = 3 + 2 √ 2 }, (u n + u -n )/2] .)

3n+1 problem as cellular automaton If one writes the digits of n in base 6, then the rule for updating the digit sequence is a cellular automaton with 7 possible colors (color 6 works as an end marker that appears to the left and right of the actual digit sequence): {a_, b_, c_}  If[b  6, If[EvenQ[a], 6, 4], 3 Mod[a, 2] + Quotient[b, 2] /. 0  6 /; a  6] The 3n+1 problem can then be viewed as a question about the existence of persistent structure in this cellular automaton.

Finding primes The sieve of Eratosthenes shown in the picture is an appropriate procedure if one wants to find every prime, but testing whether an individual number is prime can be done much more efficiently, as in PrimeQ[n] in Mathematica, for example by using Fermat's so-called little theorem that Mod[a p - 1 , p]  1 whenever p is prime.

After t steps, therefore, the configuration of such a system is given by PolynomialMod[poly t , k] .

History [of Pascal's triangle mod k ] Pascal's triangle probably dates from antiquity; it was known in China in the 1200s, and was discussed in some detail by Blaise Pascal in 1654, particularly in connection with probability theory.

Multiples of irrational numbers Instead of powers one can consider successive multiples Mod[h n, 1] of a number h .

With odd n the same turns out to be true for sequences Exp[2 π  Mod[Range[n] 2 , n]/n] —a fact used in the design of acoustic diffusers (see page 1183 ). … If Mod[p, 4]  1 JacobiSymbol sequences also satisfy Fourier[list]  list .

The colors of cells are given essentially by Mod[Multinomial[t, x, y], 2] .

The centers of an array of regular hexagons are given by Table[{i √ 3 , j}, {i, 1, m}, {j, Mod[i, 2], n, 2}] .