Powers of three in base 2

The n^th row in the pattern shown can be obtained simply as IntegerDigits[3ⁿ, 2]. Even such individual rows seem in many respects random. The picture below shows the fraction of 1's that appear on successive rows. The fraction seems to tend to 1/2.

If one looks only at the rightmost s columns of the pattern, one sees repetition—but the period of the repetition grows like 2^s. Typical vertical columns have one obvious deviation from randomness: it is twice as probable for the same colors to occur on successive steps than for opposite colors. (For multiplier m in base k, the relative frequencies of pairs {i, j} are given by Quotient[a i - j - 1 + m, k] - Quotient[m i - j - 1, k].)

The sequence Mod[3ⁿ, 2^s] obtained from the rightmost s digits corresponds to a simple linear congruential pseudorandom number generator. Such generators are widely used in practical computer systems, as discussed further on page 974. (Note that in the particular case used here, pairs of numbers Mod[{3ⁿ, 3^{n + 1}}, 2^s] always lie on lines; with multipliers other than 3, such regularities may occur for longer blocks of numbers.)

Note that if one uses base 6 rather than base 2, then as shown on page 614 powers of 3 still yield a complicated pattern, but all operations are strictly local, and the system corresponds to a cellular automaton with 6 possible colors for each cell and rule {a_, b_, c_}  3 Mod[b, 2] + Floor[c/2] (see page 1093).