[Tutor] Finding a repeating sequence of digits

Dave Angel davea at ieee.org
Sat Jan 2 13:54:57 CET 2010

Robert Berman 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.
> Robert Berman
Exactly what is your real goal?  Are you explicitly starting with 
fractions, and want to know what the repeat cycle is when that fraction 
is expressed in base 10 ?  (All rational numbers have repeating cycles, 
in any given base, but the cycle size can vary depending on the base)

Or are you starting with decimal.Decimal values, and need to investigate 
their characteristics?

Or are you really just trying to analyze strings, and looking for 
repeating patterns in them?  If this is the case, you need to define how 
many repeats constitutes "proof" that you have a cycle.  Suppose you 
have a precision of 1000, and after 995 digits, you discover the first 
five are appearing again?  That's not necessarily a cycle.  But what if 
you have 400 arbitrary digits, followed by two copies of 300 digits?  Is 
that a cycle of 300, or just a coincidence?

In any case, don't get trapped by the rounding at the end of the decimal 
value.  Your example of 45/56.0 has the last digit rounded from 5 to 6, 
so it could fool a naive implementation.

Finally, do you need better than brute force performance?  Then we need 
to know what information you really can assume.

Does the number #26 mean anything to you?


More information about the Tutor mailing list