[Tutor] Finding a repeating sequence of digits

[Shashwat Anand]

What you are searching for is sheer bruteforce however if I'm guessing it
right then you are solving Project Euler and you are thinking in wrong
direction.

On Sat, Jan 2, 2010 at 3:52 PM, spir <denis.spir at free.fr> wrote:

> 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/
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> To unsubscribe or change subscription options:
> http://mail.python.org/mailman/listinfo/tutor
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20100102/d9404265/attachment.htm>