A Procedure to Compute the Digit Sequence of a Rational Number

denominator n

137

steps

25

digit sequence of 1/137 =

1.1101111001011101011

2

×

-8

2

r	digit sequence of 1 n

This Demonstration visualizes a procedure for generating the base 2-digit sequence for the rational number

p

q

,

p=1

,

q=n

. From A New Kind of Science, p. 139: "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." On the left, the

th

k

row shows the binary digits of

r

at the

th

k

step in the algorithm, and on the right, the binary digits of

1/n

are shown vertically. Black cells represent 1's, and gray cells represent 0's.