[Tutor] Finding a repeating sequence of digits
davea at ieee.org
Sat Jan 2 13:54:57 CET 2010
Robert Berman wrote:
> 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
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