below show successive steps in a particular method for computing the base 2 digit sequence for the rational numbers p/q.

The method is essentially standard long division, although it is somewhat simpler in base 2 than in the usual case of base 10. The idea is to have a number r which essentially keeps track of the remainder at each step in the division. One starts by setting r equal to p. Then at each step, one compares the values of 2r and q. If 2r is less than q, the digit generated at that step is 0, and r is replaced by 2r. Otherwise, r is replaced by 2r – q. With this procedure, the value of r is always less than q. And as a result, the digit sequence obtained always repeats at most every q – 1 steps.

It turns out, however, that rational numbers are very unusual in having such simple digit sequences. And indeed, if one looks for example at square roots the story is completely different.

Perfect squares such as 4 = 2 × 2 and 9 = 3 × 3 are specifically set up to have square roots that are just whole numbers. But as the table at the top of the next page shows, other square roots have much more complicated digit sequences. In fact, so far as one can tell, all whole numbers other than perfect squares have square roots whose digit sequences appear completely random.


Successive steps in the computation of various rational numbers. In each case, the column on the right shows the sequence of base 2 digits in the number, while the box on the left shows the remainder at each of the steps in the computation.


Exportable Images for This Page:

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