[Tutor] Finding a repeating sequence of digits

[spir]

Robert Berman dixit:

> 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

Well, I'm not sure of what you want. An algorithm able to _guess_ whether a fraction like 1/3 is infinitely repetitive, or just to observe it? For the former, no clue. For the latter, here are some random thoughts.

(0. I guess from your words you noted that this depends on the base: 1/3 reads 0.1 in base 3.)

1. You'll need to work on the _representation_ (string), actually only on the fractional part, not on the python numbers themselves.
2. Decimals allow adjusting precision.
3. You'll need at least 2 config parameters: one to limit the size of the repetitive scheme, one to limit the position at which this scheme may start.
4. From how many repetitions on do you consider a repetitive scheme is found? (eg 0.333 is enough?)
5. At first sight, I cannot find any other method as brute force: at each pos, try each sequence size. When a repetition is found, check it repetes further, up to the number you chose at point 4.

Denis
________________________________

la vita e estrany

http://spir.wikidot.com/