[Tutor] Finding a repeating sequence of digits

[Kent Johnson]

On Fri, Jan 1, 2010 at 9:01 PM, Robert Berman <bermanrl at cfl.rr.com> wrote:
> Hi,
>
> I am trying to build an algorithm or methodology which will let me tell
> if a decimal has a repeating sequence of digits and if it does have that
> attribute, what is the sequence of digits. For example, 1/3.0 =
> 0.333333333..By eyeballing we know it has a repeating sequence and we
> know that the sequence is .3333.....A little more complex is 1/7.0 =
> 0.142857142857 but still is equivalent. A harder example is 45/56.0 =
> 0.8035714285714286. Here we have a repeating sequence but it comes after
> the first three digits.
>
> What I am looking for are ideas and suggestions looking for patterns. I
> do know I should use a relatively large precision as repeating values
> may constitute a rather long sequence. I did see, on Google, a
> suggestion to use a precision of 1000.
>
> Thank you for any and all ideas and suggestions.

I would write a program that emulates long division "by hand". At each
step of the division you get a remainder; if the remainder is 0, you
are done. If the remainder is one you have seen before, but not 0, the
fraction has started to repeat.

The remainder must always be smaller than the denominator of the
original fraction so by the pigeonhole principle the result must
either terminate or repeat with length no longer than the value of the
denominator (plus a fudge for initial conditions).

Kent